0

在两个数组中查找所有重复项的最佳算法是什么？

我能想到的是蛮力算法。

直接比较两个数组，一旦找到相同的数字，将其存储在辅助数组中。但时间复杂度为O (n 2 )。

4

4 回答 4

6
  • 将第一个数组的数字添加到哈希结构 (hashset)
  • 对于第二个数组中的每个数字，如果在哈希集中，则添加到最终数组，如果不忽略

那将是 O(n+m) （数组的大小）。

于 2012-10-13T08:07:27.873 回答
3

有一个 O(n log n) 算法。

Sort arr1 and arr2 using quick sort or merge sort

i = 0
j = 0
found = 0
while i < arr1.length and j < arr2.length:
      if (arr1[i] == arr2[j])
          found = found + 1
          i = i + 1
          j = j + 1
      else if (arr1[i] < arr2[j])
          i = i + 1
      else
          j = j + 1
于 2012-10-13T08:06:12.497 回答
2

对数组进行排序，然后同时遍历两个数组，当当前元素小于另一个时，总是推进一个数组。复杂度：O(nlogn)

于 2012-10-13T08:07:24.160 回答
2

您可以在 O(n) 时间内识别数组中的重复项。这种方法使用hashmap，这里是伪代码：

// a and b are input arrays
HashMap h
for e in a:
    if h[e] == 0:
        h[e]++
for e in b:
    if h[e] != 0:
        h[e]++
for e in h:
    if e > 1:
        print "Duplicate" + e

Hashmap[Element]是语法糖，意思是：

使用键 e 获取元素，如果不存在，则使用初始化程序 0 创建它

于 2012-10-13T08:06:28.137 回答