算法:查找恰好出现两次的元素

Question

输入一个未排序的整数数组A[1..n]只有 O(d) :(d < < n)不同的元素。

输出所有恰好出现两次的元素。

要求两种算法，一种是O(Nd)和另一个O(Nlogd) .最大数量可能非常大，因此大小为 n 的数组计算频率可能不是一个好主意。有什么想法吗？

澄清一下，“只有 O(d) :(d < < n) 个不同的元素”是指所有其他元素(不是那些 O(d) 个元素)出现了两次或更多次。

Answer 1

O(nd) 基本上是迭代所有可能的元素(O(d) of those)并计算它重复的次数。每次迭代都是 O(n)

O(nlogd) 是构建一个histogram (map:int->int) 计算每个元素在单次迭代中出现在列表中的次数。 map 是balanced Binary Search Tree基于确保 O(nlogd)。请注意，如果您使用 hash map代替树，它可以增加到 O(n) 平均情况(但 O(nd) 最坏情况)

伪代码 - O(nlogd):

map <- new tree map
for each element x in list:
 if x is in map:
     map.put(x,map.get(x)+1)
 else:
     map.put(x,1)
for each (key,value) in map:
  if value == 2:
     print key