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

发布于 2025-01-30 20:30:11 字数 285 浏览 3 评论 0原文

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

第一行是指数字10重复4次，第二行是指数字5重复三个等等。目的是对这些数字进行排序，这是以下降顺序首先重复的。我认为使用hashmap记录数据，然后将其馈送到树上，然后按值排序将是最有效的方法 - ＆gt; o（n log n），但是有更有效的方法吗？我听说使用Max-Heap解决了这个问题，但我认为堆的做得不如O（n log n）更好。

原文

I have a list of numbers, for example:

first line means the number 10 repeats 4 times, the second line means the number 5 repeats thrice and so on. The objective is to sort these numbers, the most repeated first in descending order. I think using Hashmap to record the data and then feeding it to treeset and sort by value would be the most efficient way -> O(n log n), but is there a more efficient way? I've heard this problem is solved with max-heap, but I dont think heap can do better than O(n log n).

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

只是在用心讲痛 2025-02-06 20:30:11

我认为，通过铲斗式排序，o（n）的复杂性是可能的。至少在理论上。但是，在存储桶的内存方面，它带来了额外的成本。这可能会使方法在实践中棘手。

水桶是标签。每个水桶都以相同的计数保存所有数字。为了快速访问，我们将存储桶保存在阵列列表中，每个存储库处于其计数的索引位置。

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

每个到达的数字需要O（1）进行处理，因此全部采用O（n）。

回复收藏 0 原文

寂寞花火° 2025-02-06 20:30:11

您可以获得map.entry＆lt; integer，Integer＆gt;的排序列表，例如：

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

它应该在o（n*log（n））中。

You can get a sorted list of Map.Entry<Integer,Integer> like this:

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

It should be in O(n*log(n)).

回复收藏 0 原文

涙—继续流 2025-02-06 20:30:11

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

geekforgeeks的 hashmap按值。

由于无法对hashmap进行排序，并且在linkedhashmap中的元素顺序无法更改，除非将其删除和以不同的顺序重新输入代码将内容复制到list中，然后对列表进行排序。作者希望将数据保留在hashmap中，因此将排序列表复制到新的linkedhashmap。

出于O/P的目的，将在示例具有＆lt; string，Integer＆gt;的情况下使用＆lt; integer，integer＆gt;。另外，由于所需的订单正在下降，o2和o1将在比较器的return语句中反转：

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

有数学证据，没有比较排序的运行少于O（N log N）。

(I Replaced my original answer.)

GeekForGeeks has example code for sorting a HashMap by value.

Since a HashMap can't be sorted, and the order of elements in a LinkedHashMap can't be changed unless they are removed and re-entered in a different order, the code copies the contents into a List, then sorts the list. The author(s) want to retain the data in a HashMap, so the sorted list is then copied to a new LinkedHashMap.

For the O/P's purposes, <Integer, Integer> would be used where the example has <String, Integer>. Also, since the desired order is descending, o2 and o1 would be reversed in the return statement of the comparator:

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

There are mathematical proofs that no comparison sort can run in less than O(n log n).

回复收藏 0 原文

怀中猫帐中妖 2025-02-06 20:30:11

假设数字是唯一的，

为什么要排序？只需循环遍历每个键，保存最大事件，您就可以在O（n）中获得它

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

Assuming the number is unique,

Why sort? just loop through every key save max occurence, and you’ll get it in O(n)

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

回复收藏 0 原文

~没有更多了~