Java TreeMap 获取第 K 个最小的键

Question

我正在使用 TreeMap，想要获取第 K 个最小的键。我编写了以下实现:

public static Long kthKey(TreeMap<Long, MyObject> treeMap, int kth) {
    Long currentKey = treeMap.firstKey();
    for (int i = 1; i < kth; i++) {
        currentKey = treeMap.higherKey(currentKey);
    }
    return currentKey;
}

这在内存方面非常有效，但在运行时间方面可能不太有效。

有没有更有效的方法来做到这一点？

Answer 1

如果允许使用迭代器，则可以执行此操作。

public <T> static Long kthKey(Map<T, ?> map, int kth) {
    for(T key: map.keySet())
       if(kth-- < 1) return key;
    return null;
}

一个迭代器的成本并不是那么高，如果您需要避免这种情况，我建议您查看如何调用此方法并对其进行优化，例如说你有

for (int k = 0; k < mapsize(); k++) {
    Long l = kthKey(map, k);

您可以完全消除调用此方法的需要。