java 如何在Java中的TreeMap中检索具有最大值的键？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/40576934/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to retrieve the key with a maximum value in a TreeMap in Java?
提问by Spider Man
I have a tree map declared as follows:
我有一个树形图声明如下：
TreeMap<Integer, Integer> tree = new TreeMap<Integer, Integer>();
How do I retrieve the key with the maximum value. Is there an O(1) way of achieving this. I know that maximum and minimum keys can be retrieved from a TreeMap in O(1) time as follows:
如何检索具有最大值的密钥。有没有 O(1) 的方法来实现这一点。我知道可以在 O(1) 时间内从 TreeMap 中检索最大和最小键，如下所示：
int maxKey = tree.lastEntry().getKey();
int minKey = tree.firstEntry().getKey();
Thanks for help.
感谢帮助。
采纳答案by Peter Lawrey
The collection is not sorted by value so the only way is brute force O(n) unless there is another collection with say the reverse map available.
集合不是按值排序的，所以唯一的方法是蛮力 O(n)，除非有另一个集合可以使用反向映射。
Map<Integer, Integer>map = new TreeMap<>();
int max = map.values().stream().max(Integer::compare).get();
回答by Spider Man
The answer provided by @PeterLawrey answers the question fair enough. If you are looking for a simpler implementation, here it is:
@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());
回答by Mukesh Kumar
O(1) complexity is not possible with TreeMap. you need to create one more map which uses value of first map as keys. or use BiMap
使用 TreeMap 不可能实现 O(1) 复杂度。您需要再创建一个地图，该地图使用第一个地图的值作为键。或使用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()
}
}
回答by Christian Hoffmann
Do you depend on using a TreeMap/do you fill it yourself? I ran into a similar situation and extended the TreeMap by the missing functionality:
您是否依赖于使用 TreeMap/您自己填充它？我遇到了类似的情况，并通过缺少的功能扩展了 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;
}
}
This won't decrease the complexity but depending on when and how your Map is filled having the values prepared for you when you need them might be preferable.
这不会降低复杂性，但取决于何时以及如何填充 Map，在您需要时为您准备值可能更可取。
