找到阵列中第N个最常见的数字

Question

Find the nth most frequent number in array.
(There is no limit on the range of the numbers)

我想我们可以

(i)使用C++中的地图存储每个元素的出现

(ii)在元素的出现(或频率)的线性时间内构建最大堆,然后提取到第N个元素,每次提取需要log(n)时间来进行堆积.

(iii)我们将获得第N个最常见数字的频率

(iv)然后我们可以通过哈希进行线性搜索,找到具有该频率的元素.

时间 - O(NlogN)空间 - O(N)

有没有更好的方法？

Answer 1

它可以在线性时间和空间中完成.令T为输入数组中的元素总数,我们必须从中找到第N个最常见的数字:

1. 在地图中计算并存储T中每个数字的频率.设M是数组中不同元素的总数.所以,地图的大小是M. - O(T)
2. 使用选择算法在地图中找到第N个最大频率. - O(M)

总时间= O(T)+ O(M)= O(T)

Answer 2

你的方法基本是对的。如果用所构建的堆的每个顶点所代表的数字来标记它，则可以避免最终的哈希搜索。此外，在构建堆的第五个元素时，可以不断地监视堆的第五个元素，因为在某些时候，您可能会遇到结果无法再改变并且其余计算可以被放弃的情况。但这可能不会使算法在一般情况下更快，甚至在特殊情况下也可能不会。所以你正确地回答了你自己的问题。