algorithm - 找到数组中第 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 中每个数字的出现频率并将其存储在 map 中。令 M 为数组中不同元素的总数。所以， map 的大小是M。 -- O(T)
2. 使用 Selection algorithm 在 map 中找到第 N 个最大频率. -- O(M)

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