Получить минимальное значение карты (ключ, двойной)

Question

Есть ли способ (возможно, с Google Collections) для получения минимального значения Map(Key, Double)?

Традиционным образом мне пришлось бы отсортировать карту по значениям и взять первый / последний.

Answer 1

Для этого вы можете использовать стандарт Collections#min().

Map<String, Double> map = new HashMap<String, Double>();
map.put("1.1", 1.1);
map.put("0.1", 0.1);
map.put("2.1", 2.1);

Double min = Collections.min(map.values());
System.out.println(min); // 0.1

Обновление : поскольку вам также нужен ключ, я не вижу путей в API Collections или Google Collections2, поскольку Map не является Collection. Maps#filterEntries() также не очень полезен, поскольку фактический результат известен только на конце итерации.

Тогда самым простым решением будет следующее:

Entry<String, Double> min = null;
for (Entry<String, Double> entry : map.entrySet()) {
    if (min == null || min.getValue() > entry.getValue()) {
        min = entry;
    }
}

System.out.println(min.getKey()); // 0.1

(проверка нуля на min оставлена ​​в стороне)

Answer 2

Вы все еще можете использовать Collections.min с пользовательским Comparator, чтобы получить Map.Entry с меньшим значением:

Map<String, Double> map = new HashMap<String, Double>();
map.put("1.1", 1.1);
map.put("0.1", 0.1);
map.put("2.1", 2.1);
Entry<String, Double> min = Collections.min(map.entrySet(), new Comparator<Entry<String, Double>>() {
    public int compare(Entry<String, Double> entry1, Entry<String, Double> entry2) {
        return entry1.getValue().compareTo(entry2.getValue());
    }
});
System.out.printf("%s: %f", min.getKey(), min.getValue()); // 0.1: 0.100000

С Java 8:

Entry<String, Double> min = Collections.min(map.entrySet(),
                                       Comparator.comparing(Entry::getValue));

Answer 3

Традиционно мне бы пришлось сортировать карту по значениям, и возьмите первый / последний. спасибо

Нет, ты бы не стал. Вам придется перебирать все значения и на каждом шаге сравнивать текущий элемент с наименьшим, который когда-либо видел. Это O (n) по сравнению с O (n * log (n)) для сортировки - потенциально огромная разница.

Кстати, именно так работает Collections.min().

Answer 4

Использование потоков Java 8:

return map
            .entrySet()
            .stream()
            .sorted(Comparator.comparingDouble(Map.Entry::getValue))
            .findFirst()
            .map(Map.Entry::getValue);

Или

return map
            .entrySet()
            .stream()
            .min(Comparator.comparingDouble(Map.Entry::getValue))
            .map(Map.Entry::getValue);

Но если вы хотите сделать это несколько раз, то обязательно посмотрите heap .

Answer 5

Я бы хотел использовать BiMap Google Collections:

     String minKey = HashBiMap.create(map).inverse().get(Collections.min(map.values()));

Или что-то в этом роде (не проверено).

Answer 6

В Java 8 мы можем легко получить:

Double minValue = map.entrySet().stream().min(Map.Entry.comparingByValue()).get().getValue();
Double maxValue = map.entrySet().stream().max(Map.Entry.comparingByValue()).get().getValue();

Answer 7

Использование Java 8 (и статический импорт). Мы можем сделать решение @ superfav намного аккуратнее:

Map<String, Double> myMap;
String theKeyWithHighestValue = Collections.min(myMap.entrySet(), comparingDouble(Entry::getValue)).getKey()

Answer 8

Чтобы сделать это эффективно, вы можете определить свою собственную структуру данных, такую, чтобы она реализовывала интерфейс Map, но также допускала эффективную операцию getMin ().

Это можно сделать с помощью двух внутренних структур данных: карты и дерева (или структуры данных кучи). Каждый раз, когда добавляется новая пара (K, V), добавляйте их на карту, а также в дерево (как одну запись). Это позволяет O (1) время для операций get (Key) и O (log n) время для операций добавления, удаления и getMin.

Answer 9

Java8 One-Liner

Key key = Collections.min(map.entrySet(), Map.Entry.comparingByValue).getKey()