ios - Swift - 性能明智 - 比较两个数组并获得每个数组的差异和两个数组的共同点

Question

祝你今天过得愉快。

我正在尝试了解执行以下操作的最快方法是什么:

假设我有这两个数组:

var firstArray = ["a","b","c"]
var secondArray = ["a","d","e"]

我想得到一个输出:

1) Array inside firstArray 但不在 secondArray 中的对象.
1) Array inside secondArray 但不在 firstArray 中的对象。
3)firstArray和secondArray之间<​​strong>common对象的Array。

所以基本上输出是:

1) ["b","c"]
2) ["d","e"]
3) ["a"]

这里的主要问题是了解什么是最有效的方法。非常感谢!

Answer 1

如果您的数组已排序并且每个数组中的项目都是唯一的，那么最快的方法是每个项目只处理一次。首先比较每个数组中的第一项；如果它们相等，则将其放入公共(public)数组，然后继续处理第二项。如果一个项目小于另一个项目，它进入较小项目的唯一数组，然后您移动到较小数组中的下一个项目。继续此过程，直到用完一个数组的项，然后将第二个数组的剩余项放入该数组的唯一项数组中。

var i = 0
var j = 0

let a = ["a", "b", "c"]
let b = ["a", "d", "e"]

var aUnique = [String]()
var bUnique = [String]()
var common = [String]()

while i < a.count && j < b.count {
    if a[i] == b[j] {
        common.append(a[i])
        i += 1
        j += 1
    } else if a[i] < b[j] {
        aUnique.append(a[i])
        i += 1
    } else {
        bUnique.append(b[j])
        j += 1
    }
}

if i < a.count {
    // put remaining items into aUnique
    aUnique += a[i ..< a.count]
} else if j < b.count {
    // put remaining items into bUnique
    bUnique += b[j ..< b.count]
}

print(common)  // ["a"]
print(aUnique) // ["b", "c"]
print(bUnique) // ["d", "e"]

---

分析

• 此算法每次通过循环将一项附加到数组之一。如果两个数组相对于彼此唯一，或者只有最后一项是公共(public)的，它将最多循环 a.count + b.count - 1 次。
• 如果两个数组相同，它只会循环 a.count 次。
• 如果数组b 的所有元素都大于数组a 的元素，它只会循环a.count 次。如果数组 a 的所有元素都大于数组 b 的元素，它只会循环 b.count 次。