我有一個數字串列，例如：
10 4
5 3
7 1
-2 2
第一行表示數字10重復4次數，第二行表示數字5重復三次，依此類推。目標是對這些數字進行排序，重復次數最多的數字按降序排列。我認為使用 Hashmap 記錄資料，然后將其提供給樹集并按值排序將是最有效的方式 -> O(n log n)，但有沒有更有效的方式？我聽說這個問題是用 max-heap 解決的，但我認為堆不能比 O(n log n) 做得更好。
uj5u.com熱心網友回復：
（我替換了我原來的答案。）
GeekForGeeks 有按值排序的示例代碼HashMap。
由于 aHashMap無法排序，并且 a 中元素的順序LinkedHashMap不能更改，除非它們被洗掉并以不同的順序重新輸入，因此代碼將內容復制到 aList中，然后對串列進行排序。作者希望將資料保留在 a 中HashMap，因此將排序串列復制到新的LinkedHashMap.
出于 O/P 的目的，<Integer, Integer>將在示例具有<String, Integer>. 此外，由于所需的順序是降序的，o2并且o1會在return比較器的陳述句中反轉：
return (o2.getValue()).compareTo(o1.getValue());
有數學證明，沒有任何比較排序可以在小于 O(n log n) 的時間內運行。
uj5u.com熱心網友回復：
假設編號是唯一的，
為什么要排序？只需遍歷每個鍵保存最大出現次數，您將在 O(n) 中得到它
maxNum = 0
maxValue = -1
loop numbers:
if (numbers[i].value > maxValue) :
maxValue = numbers[i].value
maxNum = numbers[i].key
return maxNum;
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/480245.html
上一篇：這張圖代表什么時間復雜度？