在数组中找到第N个最频繁的数字 [英] Find the N-th most frequent number in the array

问题描述

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

我认为我们可以

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

(i) store the occurence of every element using maps in C++

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

(ii) build a Max-heap in linear time of the occurences(or frequence) of element and then extract upto the N-th element, Each extraction takes log(n) time to heapify.

(iii)我们将获得第N个最频繁出现的数字的频率

(iii) we will get the frequency of the N-th most frequent number

(iv)然后我们可以在散列中进行线性搜索以找到具有此频率的元素.

(iv) then we can linear search through the hash to find the element having this frequency.

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

Time - O(NlogN) Space - O(N)

有更好的方法吗?

推荐答案

您的方法基本上是正确的.如果用所表示的堆号标记构造堆的每个顶点，则可以避免最终的哈希搜索.此外，在构建堆的第五个元素时，可能会一直保持监视，因为在某些时候，您可能会遇到结果不再更改且其余计算可能被丢弃的情况.但这在一般情况下可能不会使算法更快，甚至在特殊情况下也可能不会.因此，您正确回答了自己的问题.

Your method is basically right. You would avoid final hash search if you mark each vertex of the constructed heap with the number it represents. Moreover, it is possible to constantly keep watch on the fifth element of the heap as you are building it, because at some point you can get to a situation where the outcome cannot change anymore and the rest of the computation can be dropped. But this would probably not make the algorithm faster in the general case, and maybe not even in special cases. So you answered your own question correctly.

这篇关于在数组中找到第N个最频繁的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！