7 
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)

有没有更好的方法？

4

4 回答 4

8

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

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

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

于 2012-08-01T13:15:37.163 回答
3

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

于 2012-06-10T02:37:55.677 回答
1

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

1）如果您知道所有数字都将从 0 到 1000，您只需创建一个包含 1000 个零（出现）的数组，循环遍历您的数组并增加正确的出现位置。然后对这些出现进行排序并选择第 N 个值。

2）你有一个“袋子”的独特物品，你循环你的数字，检查那个数字是否在一个袋子里，如果没有，你添加它，如果它在这里，你只是增加出现的次数。然后你从中选择第 N 个最小的数字。

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

问题是“第 N 次最频繁”，所以我认为你不能避免排序（或聪明的数据结构），所以最好的复杂度不能比 O(n*log(n)) 好。

于 2012-06-10T02:32:30.437 回答
1

刚刚用Java8写了一个方法：这不是一个有效的解决方案。

  • 为每个元素创建频率图
  • 根据值以相反的顺序对地图内容进行排序。

  • 跳过第 (N-1) 个元素，然后找到第一个元素

    private static Integer findMostNthFrequentElement(int[] inputs, int frequency) {
    return Arrays.stream(inputs).boxed()
        .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
        .entrySet().stream().sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
        .skip(frequency - 1).findFirst().get().getKey();
}
于 2018-12-15T19:24:02.913 回答