计算大数组中的唯一元素

Question

我的一位同事在接受采访时被问到了问题.

给定一个存储unsigned int的巨大数组.数组长度为100000000.找到计算数组中唯一元素数的有效方法.
例如,arr = {2,34,5,6,7,2,2,5,1,34,5} O/p:2的计数是3,34的计数是2,依此类推.

这样做的有效算法是什么？我认为首先字典/哈希将是一个选项,但由于数组非常大,它是无效的.有没有办法做到这一点？

谢谢,chota

Answer 1

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

Answer 2

许多其他海报建议对数据进行排序,然后查找相邻值的数量,但没有人提到使用基数排序来使运行时为O(n lg U)(其中U是数组中的最大值) O(n lg n).由于lg U = O(lg n),假设整数占用一个机器字,这种方法渐近比heapsort更快.

在面试中,非比较种类总是很有趣.:-)

Answer 3

将其排序，然后从头开始扫描以确定每个项目的计数。

这种方法不需要额外的存储，并且可以在 O(n log n) 时间内完成（对于排序）。