问算法-先排序最重复的数(降序)

EN

(我替换了原来的答案。)

GeekForGeeks有example code for sorting a HashMap by value。

由于HashMap无法排序，并且LinkedHashMap中元素的顺序不能更改，除非它们被移除并以不同的顺序重新输入，所以代码将内容复制到List中，然后对列表进行排序。作者希望将数据保留在HashMap中，因此排序后的列表将被复制到新的LinkedHashMap中。

为了实现O/P的目的，将在示例有<Integer, Integer>的情况下使用<String, Integer>。另外，由于所需的顺序是递减的，所以在比较器的o2语句中，o1和return语句将相反：

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

有数学证明，比较排序不能在小于O(n log )的范围内运行。

我认为用桶式排序，O(N)复杂度是可能的。至少在理论上。但是，在存储桶的内存方面，它带来了额外的成本。这可能使这一做法在实践中难以解决。

水桶是HashSets。每个桶都有相同计数的所有数字。为了快速访问，我们将桶保存在一个ArrayList中，每个桶位于其计数的索引位置。

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

每个到达的数字都需要O(1)来处理，所以都采用O(N)。

您可以获得如下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))中。