比较排序数组 - nlogn

Question

我有 2 个 int 数组，我需要在 O(nlogn) 中打印所有相同的整数数组未排序，排序后可以是:

X [ 1,2,3,4,5,6,7,8,9]
Y [1,2,8,9]

所以只检查到第 4 个位置(较小数组的大小)不是一个选项。

我需要使用什么样的循环\方程，所以它是 nlogn？如果我将运行 for 直到较小数组的最后一个值 - 它仍然是 nlogn -我怎样才能只取\到达arraya中的最后一个整数而不运行到它的末尾？

Answer 1

我希望这是一个足够的提示......

数组排序后，只需“并排”遍历数组。跟踪每个数组的“当前”元素(X 和 Y)。您可以使用每个数组的索引变量或使用指针来执行此操作。就个人而言，我发现使用指针更容易，但您或您的 friend 可能有不同的偏好。

对于每对“当前”元素，如果元素匹配则打印值。然后考虑需要做什么，如果有的话，移动到每个数组的下一个元素(对于元素不匹配的情况以及它们匹配的情况)。只有三种情况:

1. x[cur_x] == y[cur_y]
2. x[cur_x] < y[cur_y]
3. y[cur_y] < x[cur_x]

因此确定在每种情况下应该做什么应该不会太困难。

在 O(n log n) 操作中对数组进行排序。遍历数组是一个 O(n) 操作，所以它总共是一个 O(n) + O(n log n) 操作，它减少到 O(n log n)。也就是说，操作的整体时间复杂度是由排序操作决定的。

使用二进制搜索也可以，但它可能会稍微复杂一些 - 特别是在需要时正确处理数组中的重复元素(并且取决于根据要求“正确”可能意味着什么)。