Find minimum value in a map java

Question

I need to find min values in a map. How i can do? I can't use any data structure and i have to make in O(n) time. This code not work..but can be a a starting point I can't use java 8.

 Entry<K, V> min=null;
    for (Entry<K, V> entry : M.entries()) {
        min=entry;
        if(c.compare(min.getValue(),entry.getValue())>0){
            min=entry;
        }
        System.out.println("MIN "+min);
    }

Go through this link http://stackoverflow.com/questions/218384/what-is-a-null-pointer-exception-and-how-do-i-fix-it — Tunaki, May 20 '16 at 13:53

user902383 · Accepted Answer · 2016-05-20T14:47:30.980

1

Simple java8 solution for map Map<Object,Integer> map = new HashMap<>();

map.values().stream().min(Integer::compare).get();

Edit As @Andreas pointed out, there was request for using comparator, so this is solution for Java 8 which finds smallest value

public static <K, V> V min8(Map<K, V> map, Comparator<V> comp) {
    return map.values().stream().min(comp).get();
}

and this is solution for Java 7 for finding entry with smallest value

public static <K, V> Entry<K, V> min(Map<K, V> map, Comparator<V> comp) {
        Iterator<Entry<K, V>> entries = map.entrySet().iterator();
        if (!entries.hasNext()) {
            return null;
        }
        Entry<K, V> min;
        for (min = entries.next(); entries.hasNext();) {
            Entry<K, V> value = entries.next();
            if (comp.compare(value.getValue(), min.getValue()) < 0) {
                min = value;
            }
        }
        return min;
    }

my initial solution was very close to @Andreas, so i decide to change and use for loop with itterator.

edited May 20 '16 at 14:47

answered May 20 '16 at 13:55

user902383

8,420
8
43
63

I can't use java 8 – Filomena Del Sorbo May 20 '16 at 13:58
2

@FilomenaDelSorbo That would have been a relevant piece of information in the question, don't you think? – Andreas May 20 '16 at 14:01
Both options are assuming that value is an `Integer`. The fact that question uses a `Comparator` (variable `c`) would indicate otherwise. Also, question seems to seek the minimum `Entry` (key + value), not just the minimum value. – Andreas May 20 '16 at 14:09
@Andreas good point, fixed for java 7, and too lazy to fix it for java 8. which i think is not relevant as op does not use java 8 – user902383 May 20 '16 at 14:51

Andreas · Answer 2 · 2016-05-20T14:14:51.653

If you always set min = entry in the beginning of the loop, you're always comparing the entry to itself. Remove that line, then also guard against the initial null value of min, and you get:

Entry<K, V> min = null;
for (Entry<K, V> entry : M.entries()) {
    if (min == null || c.compare(min.getValue(), entry.getValue()) > 0) {
        min = entry;
    }
}

If you only need the value, not the key too, then use the values() call to iterate:

V min = null;
for (V value : M.values()) {
    if (min == null || c.compare(min, value) > 0) {
        min = entry;
    }
}

Of course, in both cases it is assumed that no value in the Map will be null. A null value would cause NullPointerException, unless the Comparator can handle them.

Find minimum value in a map java

2 Answers2