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)
有更好的方法吗？
它可以在线性时间和空间内完成。令 T 为输入数组中的元素总数，我们必须从中找到第 N 个最常见的数字：
- 计算 T 中每个数字的出现频率并将其存储在映射中。令 M 为数组中不同元素的总数。所以，地图的大小是 M。 -- O(T)
- 使用以下命令查找地图中的第 N 个最大频率选择算法 http://en.wikipedia.org/wiki/Selection_algorithm。 -- O(M)
总时间 = O(T) + O(M) = O(T)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
