5

可能重复：
两个排序数组的交集

我们有两个排序数组 A 和 B，除了将一个与其他数组中的所有元素进行比较之外，如何设计一个最佳算法来找到具有它们共同元素的数组？

4

3 回答 3

32

持有两个指针：每个数组一个。

i <- 0, j <- 0
repeat while i < length(arr1) and j < length(arr2):
    if arr1[i] > arr2[j]: increase j
    else if arr1[i] < arr2[j]: increase i
    else : output arr[i], increase both pointers

这个想法是，如果对数据进行排序，如果元素在一个数组中“太大”，那么对于数组中剩余的所有其他元素来说，它将“太大”——因为它是排序的。

此解决方案需要对数据进行一次遍历。O(n)（也有很好的常数）。

于 2012-10-20T23:43:07.667 回答
10

如果两个数组（例如，A有N元素和B有M元素）的长度相似，那么最好的方法是在另一个数组中对一个数组的元素执行线性搜索。当然，由于数组已排序，下一次搜索应该从上一次搜索停止的地方开始。这是“排序数组合并”算法中使用的经典原理。上的复杂性O(N + M)。

如果长度明显不同（例如M << N），那么更优化的方法是遍历较短数组的元素并使用二分搜索在较长数组中查找这些值。复杂性就是O(M * log N)这种情况。

如您所见O(M * log N)，O(N + M)如果M比 小得多，则比 好N，否则更糟。

应该触发从一种方法切换到另一种方法的阵列大小的差异取决于一些实际考虑。如果应该根据您的数据的实际实验来选择。

这两种方法（线性和二进制搜索）可以“混合”成一个算法。让我们假设M <= N。在这种情况下，让我们选择step value S = [N / M]。您从数组中获取第一个元素，并使用 step对该数组中的元素A执行跨式线性搜索，这意味着您检查元素等等。一旦找到可能包含您正在搜索的元素的索引范围，您就切换到该数组段内的二进制搜索。完毕。对 的下一个元素的跨接线性搜索从前一个搜索停止的地方开始。（作为旁注，选择BSB[0], B[S], B[2*S], B[3*S], ...[S*i, S*(i+1)]BAS等于 2 的幂）。

这种“混合”算法是现有的两个排序数组的最渐近最优搜索/合并算法。然而，在实践中，根据数组的相对大小选择二进制或线性搜索的更简单方法效果很好。

于 2012-10-20T23:57:34.280 回答
1

除了将一个与其他数组中的所有元素进行比较

您必须比较 A[] 和 B[] 才能知道它们是相同的——除非您非常了解它们可以保存什么样的数据。比较的性质可能有很多解决方案，可以根据需要进行优化。

如果数组是非常严格地创建的，即只有已知模式的连续值并且总是从已知点开始，您只需查看每个数组的长度并知道所有项目是否都是公共的。

不幸的是，这听起来不像是一个非常现实或有用的数组，因此您要返回检查 B[] 中的 A[i]

于 2012-10-20T23:51:24.377 回答