如何在 Java 的 TreeMap 中检索具有最大值的键？

Question

我有一个树状图声明如下：

TreeMap<Integer, Integer> tree = new TreeMap<Integer, Integer>();

如何检索具有最大值的密钥。有没有一种 O(1) 的方法来实现这个。我知道可以在 O(1) 时间内从 TreeMap 中检索最大和最小键，如下所示：

int maxKey = tree.lastEntry().getKey();
int minKey = tree.firstEntry().getKey();

感谢您的帮助。

Answer 1

该集合未按值排序，因此唯一的方法是暴力 O(n)，除非有另一个集合可以使用反向映射。

Map<Integer, Integer>map = new TreeMap<>();
int max = map.values().stream().max(Integer::compare).get();

Answer 2

@PeterLawrey 提供的答案很公平地回答了这个问题。如果您正在寻找更简单的实现，这里是：

TreeMap<Integer, Integer> tree = new TreeMap<Integer, Integer>();
// populate the tree with values
Map.Entry<Integer, Integer> maxEntry = null;
for(Map.Entry<Integer, Integer> entry : tree.entrySet()){
   if(maxEntry == null || entry.getValue().compareTo(maxEntry.getValue()) > 0)
      maxEntry = entry;
}

System.out.println("The key with maximum value is : " + maxEntry.getKey());

Answer 3

O(1) 复杂度对于 TreeMap 是不可能的。您需要再创建一个使用第一个地图的值作为键的地图。或者使用 BiMap

public TreeBiMap implements Map {
   private Map<Integer, Integer> map;
   private Map<Integer, Integer> reverseMap;
   public TreeBiMap() {
     map = new TreeMap<>();
     reverseMap = new TreeMap<>();
   }

   public void put(Integer key, Integer value) {
      map.put(key, value);
      reverseMap.put(value, key);
   }

   public Integer getMaxValue() {
      return reverseMap.lastEntry().getKey()
   }

}

Answer 4

你靠用TreeMap/do你自己填吗？我运行遇到了类似的情况，并通过缺少的功能扩展了 TreeMap：

public class TreeMapInteger<T> extends TreeMap<Integer,T> {

    private static final long serialVersionUID = -1193822925120665963L;

    private int minKey = Integer.MAX_VALUE;
    private int maxKey = Integer.MIN_VALUE;

    @Override
    public T put(Integer key, T value) {

        if(key > maxKey) {
            maxKey = key;
        }

        if(key < minKey) {
            minKey = key;
        }

        return super.put(key, value);

    }

    public int getMaxKey() {
        return maxKey;
    }

    public int getMinKey() {
        return minKey;
    }

}

这不会降低复杂性，但取决于何时以及如何填充您的地图，在您需要时为您准备好值可能更可取。

Answer 5

正如其他人所说，您基本上必须迭代每个映射条目并找到具有最大值的条目。

请注意，您在 post 中犯了一个错误。

I know that maximum and minimum keys can be retrieved from a TreeMap in O(1) time as follows:

int maxKey = tree.lastEntry().getKey();
int minKey = tree.firstEntry().getKey();

我觉得时间复杂度应该是O(lgn).

getLastEntry的源代码：

/**
     * Returns the last Entry in the TreeMap (according to the TreeMap's
     * key-sort function).  Returns null if the TreeMap is empty.
     */
    final Entry<K,V> getLastEntry() {
        Entry<K,V> p = root;
        if (p != null)
            while (p.right != null)
                p = p.right;
        return p;
    }

另请参阅this post in SO

如何在 Java 的 TreeMap 中检索具有最大值的键？

How to retrieve the key with a maximum value in a TreeMap in Java?

java

treemap