在地图中查找最小值的有效方法 [英] Efficient way to find min value in Map

问题描述

我正尝试在如下所示的Map中找到具有最小值的key.

I am trying to find key with minimum value in Map shown below.

 Map<Node, Integer> freeMap = new TreeMap<>();
 Node minNode = null;
        for (Map.Entry<Node, Integer> entry : freeMap.entrySet()) {
            if (minNode == null) {
                minNode = entry.getKey();
            } else {
                if (entry.getValue() < freeMap.get(minNode)) {
                    minNode = entry.getKey();
                }
            }
        }

首先，有没有一种直接方法可以找到比使用foreach循环最少的value最小的key.其次，您能否建议一些替代的数据结构方法，该方法可用于存储Node对象和关联的Integer值，因此我可以在恒定时间O(1)中以最小值获取entry.

Firstly, Is there a straight forward way to find key with minimum value than using foreach loop. Secondly, can you suggest some alternate data structure approach which can be used to store a Node object and an associated Integer value, so I can fetch entry with minimum value in constant time O(1).

推荐答案

如果您的目标是提高时间的复杂度，则实际上只有一个可能的变化，即从O(n log n)到O(n n):

If your goal is to improve time complexity, there's really only one possible change, from O(n log n) to O(n):

 Map<Node, Integer> freeMap = new TreeMap<>();
 Map.Entry<Node, Integer> minEntry = null;
 for (Map.Entry<Node, Integer> entry : freeMap.entrySet()) {
   if (minEntry == null || entry.getValue() < minEntry.getValue()) {
      minEntry = entry;
   }
 }
 Node minNode = minEntry.getKey();

这篇关于在地图中查找最小值的有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！