算法 - 首先对最重复的数字进行排序（降序）

Question

我有一个数字列表，例如：

第一行表示数字10重复4次，第二行表示数字5重复三次，依此类推。 objective就是对这些数字进行排序，最重复的排在最前面。我认为使用 Hashmap 记录数据然后将其提供给树集并按值排序将是最有效的方法 -> O(n log n)，但是有没有更有效的方法？我听说这个问题用 max-heap 解决了，但我认为堆不能比 O(n log n) 做得更好。

Answer 1

假设号码是唯一的，

为什么排序？只需遍历每个键保存最大出现次数，您将在 O(n)

中得到它

maxNum = 0
maxValue = -1
loop numbers:
   if (numbers[i].value > maxValue) :
     maxValue = numbers[i].value
     maxNum = numbers[i].key
return maxNum;

Answer 2

（我替换了原来的答案。）

GeekForGeeks 有 example code for sorting a HashMap by value.

由于无法对 HashMap 进行排序，并且无法更改 LinkedHashMap 中元素的顺序，除非将它们移除并以不同的顺序排列 re-entered，代码将内容复制到 List 中，然后对列表进行排序。作者想保留HashMap中的数据，所以排序后的列表被复制到一个新的LinkedHashMap.

出于 O/P 的目的，<Integer, Integer> 将用于示例 <String, Integer> 的地方。此外，由于所需的顺序是降序的，因此 o2 和 o1 将在比较器的 return 语句中反转：

return (o2.getValue()).compareTo(o1.getValue());

有数学证明，没有比较排序可以运行在小于 O(n log n) 的时间内。

Answer 3

我认为使用 bucket-style 排序，O(N) 复杂度是可能的。至少在理论上。但它会带来存储桶内存方面的额外成本。这可能会使该方法在实践中难以处理。

桶是哈希集。每个桶都包含具有相同计数的所有数字。为了快速访问，我们将存储桶保存在 ArrayList 中，每个存储桶都位于其计数的索引位置。

与 OP 一样，我们使用 HashMap 将数字与计数器相关联。当一个数字到达时，我们增加计数器并将数字从旧计数的桶移动到新计数的桶。这使数字始终保持排序。

每个到达的号码都需要 O(1) 来处理，所以都需要 O(N)。

Answer 4

您可以获得 Map.Entry<Integer,Integer> 的排序列表，如下所示：

    List<Map.Entry<Integer,Integer>> entries = map.entrySet()
            .stream()
            .sorted((a,b)->a.getValue().compareTo(b.getValue()))
            .collect(Collectors.toList());

它应该在 O(n*log(n)) 中。

算法 - 首先对最重复的数字进行排序（降序）

algorithm - sort most repeated number first (descending order)

java

sorting

algorithm

heap