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

Question

希望您度过愉快的一天。

我试图了解执行以下操作的最快方法是什么：

假设我有这两个Arrays：

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

我想得到以下输出：

1)位于 内部但不位于 中Array的对象。 1)位于 内部但不位于 中的对象。 3)和之间的共同对象。 firstArray secondArray
Array secondArray firstArray
ArrayfirstArraysecondArray

所以基本上输出是：

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

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

Answer 1

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

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"]

分析

• 该算法每次循环时都会将一项添加到其中一个数组中。a.count + b.count - 1如果两个数组相对于彼此是唯一的，或者只有它们的最后一项是公共的，那么大多数情况下它都会循环。
• 如果两个数组相同，则只会循环a.count一次。
• 如果 array 的所有元素b都大于 array 的元素a，则只会循环a.count一次。如果 array 的所有元素a都大于 array 的元素b，则只会循环b.count一次。