java - TreeMap : Sort values of a map with keys moving along with values

Question

我有以下 TreeMap:

TreeMap<Integer, Double> map;

Double 值不是唯一的。

我使用 Integer 键和函数 firstEntry() 和 higherEntry() 遍历映射并修改 Double 值。

现在我想按 Double 值递减的顺序列出对的值。执行此操作的最佳方法是什么？

那些 Integer 键对我很重要，因为 Double 值不是唯一的，所以我不能有 Double 键。

更新:更多说明这是经典问题。可以说学生的 rollnos 是关键，他们的百分比是值(value)。现在按百分比排序然后我们应该能够分辨出它是谁的百分比。因此我需要整数键。

Answer 1

明显的解决方案是获取 double 的集合( 可能通过 entrySet 然后是 getValue - TreeMap 类有一个 values() 方法，您可以只使用它)，然后继续对它们进行排序(使用 Collections.sort 或 Arrays.sort)- 这将，但是，需要 O(n logn) 时间。

我不确定您能否以更智能(== 更快)的方式完成它，除非您完全更改数据结构。然而，我看到这种情况发生在另一个数据结构上的唯一方法是对整数和 double 进行包装并编写两个比较器 - 一个比较 integer 和一个首先比较 double 然后是 integer。您使用的原始 TreeMap 是相同的，但您可以从中分离另一个 TreeMap，由第二个比较器排序。尽管如此，分离仍然需要 O(n logn) 时间。