通过使用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()); 
}