查找数组中最频繁的第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

你的方法基本上是正确的。如果用所构造的堆的每个顶点标记它所表示的数字，就可以避免最终的散列搜索。此外，在构建堆的第五个元素时，可以不断地监视它，因为在某些情况下，结果不能再更改，而计算的其余部分可能会被丢弃。但这可能不会使算法在一般情况下更快，甚至在特殊情况下也不会。所以你回答对了你自己的问题。

Answer 2

它可以在线性时间和空间内完成。设T是输入数组中的元素总数，我们必须从中找出最频繁的第N个数字：

1. 计算T中每个数字的频率，并将其存储在映射中。设M是数组中不同元素的总数。因此，映射的大小是M。-- O(T)
2. 使用Selection algorithm在映射中找到第N个最大频率。-- O(M)

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

Answer 3

这取决于你是想要最有效的方法，还是最容易编写的方法。

1)如果你知道所有的数字都是从0到1000，你只需要创建一个1000个零(事件)的数组，循环你的数组并递增正确的事件位置。然后对这些实例进行排序，并选择第N个值。

2)你有一个唯一项的“包”，你循环你的数字，检查这个数字是否在包中，如果不在包中，你添加它，如果它在这里，你只是增加出现的次数。然后从其中选择一个第N个最小的数字。

Bag可以是线性数组、BST或Dictionary (哈希表)。

问题是“第N次最频繁”，所以我认为你无法避免排序(或巧妙的数据结构)，所以最好的复杂度不会比O(n*(N))更好。