arrays - 计算大数组中的唯一元素

Question

我的一位同事在面试中被问到这个问题。

Given a huge array which stores unsigned int. Length of array is 100000000. Find the effective way to count the unique number of elements present in the array.

例如 arr = {2,34,5,6,7,2,2,5,1,34,5}

O/p: 2 的个数是 3，34 的个数是 2，依此类推。

执行此操作的有效算法是什么？我一开始以为字典/哈希是一种选择，但由于数组非常大，所以效率很低。有什么办法吗？

Answer 1

堆排序是 O(nlogn) 并且就地排序。在处理大型数据集时，就地是必要的。排序后，您可以通过数组计算每个值的出现次数。因为数组是排序的，所以一旦值发生变化，您就会知道您已经看到所有出现的前一个值。