通過使用O（n log n）複雜度對值進行排序java HashMap複雜度

Question

我知道這個問題已被詢問並回答了很多次。但幾乎所有的解決方案的計算複雜度爲O（n^2）。

我正在尋找O（n log n）複雜度的解決方案。有人可以建議嗎？

由於堆， 切塔尼亞

Answer 1

複製的條目到List，排序List由值;複製回LinkedHashMap。我認爲一個更好的解決方案甚至是不可能的。

List<Entry<K, V>> entries = new ArrayList<Entry<K, V>>(map.entrySet()); 
Collections.sort(entries, new Comparator<Entry<K, V>>() { 
    public int compare(Entry<K, V> left, Entry<K, V> right) { 
    return left.getValue().compareTo(right.getValue()); 
    } 
} 
Map<K, V> sortedMap = new LinkedHashMap<K, V>(entries.size()); 
for (Entry<K, V> entry : entries) { 
    sortedMap.put(entry.getKey(), entry.getValue()); 
}