输入一个未排序的整数数组A[1..n]只有 O(d) :(d < < n)不同的元素。
输出所有恰好出现两次的元素。
要求两种算法，一种是O(Nd)和另一个O(Nlogd) .最大数量可能非常大，因此大小为 n 的数组计算频率可能不是一个好主意。有什么想法吗？
澄清一下，“只有 O(d) :(d < < n) 个不同的元素”是指所有其他元素(不是那些 O(d) 个元素)出现了两次或更多次。
最佳答案
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
关于算法:查找恰好出现两次的元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14137586/