Java Map считает несуществующие values - задача с Codewars 6 kyu

Question

Не получается продвинуться в решении следующей задачи с Codewars:

Winter is coming, you must prepare your ski holidays. The objective of this kata is to determine the number of pair of gloves you can constitute from the gloves you have in your drawer.Given an array describing the color of each glove, return the number of pairs you can constitute, assuming that only gloves of the same color can form pairs.

Examples: input = ["red", "green", "red", "blue", "blue"]

result = 2 (1 red pair + 1 blue pair)

input = ["red", "red", "red", "red", "red", "red"]

result = 3 (3 red pairs)

Проблема: Map записывает гораздо большие значения в value, чем необходимо.

Код:

import java.util.Map;
import java.util.HashMap;
import java.security.KeyStore;
        
class Kata {
    public static int numberOfPairs(String[] gloves) {
        int numberOfPairs = 0;
        if (gloves.length == 0) {
            return numberOfPairs;
        }
    
        Map<String, Integer> map = new HashMap<>();
        
        for (var i = 0; i < gloves.length; i++) {
            map.putIfAbsent(gloves[i], 0);
        } 

        for (var i = 0; i < gloves.length; i++) {
            for(Map.Entry<String, Integer> entry : map.entrySet()) {
                if (map.containsKey(gloves[i])) {
                    int val = entry.getValue();
                    map.put(gloves[i], val + 1);
                } 
            }
        }
        int summ = 0;

        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() >= 2) {
                summ = summ + entry.getValue();
            } 
        }     
        
        if (summ % 2 == 0) {
            numberOfPairs = summ / 2;
        } else if (summ % 2 != 0) {
            numberOfPairs = summ / 2 - 1;
        }
        return numberOfPairs;
    }
}

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

Answer 1

Уберите внутренний цикл

for(var i = 0; i < gloves.length; i++) {
>>>>> Этот    for(Map.Entry<String, Integer> entry : map.entrySet()) {

Answer 2

Проблема Map записывает гораздо большие значения в value, чем необходимо сформулирована неверно, так как прежде всего некорректна логика представленного кода.

Даже если убрать ненужный вложенный цикл при подсчёте частоты вхождений цвета перчаток с излишней проверкой map.containsKey и использовать эффективное заполнение карты частот при помощи Map::merge:

// ...
    Map<String, Integer> map = new HashMap<>();
    for (var g : gloves) {
        map.merge(g, 1, Integer::sum);
    }

дальнейшие вычисления общей суммы некорректны, несмотря на то, что они вернут правильные результаты для указанных тестовых данных:

System.out.println("mix: " + numberOfPairs("red", "green", "red", "blue", "blue"));  // mix: 2
System.out.println("red: " + numberOfPairs("red", "red", "red", "red", "red", "red")); // red: 3

так как если слегка изменить тестовые данные, получатся неверные результаты:

// добавим одну красную и синюю перчатку
System.out.println("mix2: " + numberOfPairs("red", "green", "red", "blue", "blue", "red", "blue"));
// добавим одну красную перчатку
System.out.println("red2: " + numberOfPairs("red", "red", "red", "red", "red", "red", "red"));

получим "прирост" пар в первом случае и "пропажу" одной пары во втором случае:

mix2: 3
red2: 2

Для корректного решения достаточно было бы просто просуммировать частоты для каждого цвета, делённые на 2:

public static int numberOfPairs(String ... gloves) {
    if (gloves.length < 2) {
        return 0;
    }
    Map<String, Integer> map = new HashMap<>();
    for (var g : gloves) {
        map.merge(g, 1, Integer::sum);
    }
    int sum = 0;
    for (var freq : map.values()) {
        sum += freq / 2;
    }
    return sum;        
}

Аналогичное решение с использованием Stream API:

public static int numberOfPairs(String ... gloves) {
    return gloves.length < 2 ? 0 :
        Arrays.stream(gloves)
        .collect(Collectors.groupingBy(g -> g, Collectors.summingInt(g -> 1)))
        .values()
        .stream()
        .mapToInt(freq -> freq / 2)
        .sum();
}

Результаты тестов:

System.out.println("mix1: " + numberOfPairs("red", "green", "red", "blue", "blue"));
// добавим одну красную и синюю перчатку
System.out.println("mix2: " + numberOfPairs("red", "green", "red", "blue", "blue", "red", "blue"));

System.out.println("red1: " + numberOfPairs("red", "red", "red", "red", "red", "red"));
// добавим одну красную перчатку
System.out.println("red2: " + numberOfPairs("red", "red", "red", "red", "red", "red", "red"));

mix1: 2
mix2: 2
red1: 3
red2: 3

БЛОГ НА HUSL

Java Map считает несуществующие values - задача с Codewars 6 kyu

Ответы (2 шт):