Алгоритм подсчёта вхождений элементов списка

45. Подсчитать количество вхождений элементов списка

Условие задачи:
Необходимо реализовать метод, который принимает список Integer и возвращает структуру, содержащую уникальные элементы и количество их вхождений.

Код:

public class Utils {

    // Пример:
    // 1 2 11 2 11 9 11 1 2 3
    //
    // Результат:
    // 1  -> 2
    // 2  -> 3
    // 11 -> 3
    // 9  -> 1
    // 3  -> 1

    public Map<Integer, Integer> countElementItems(
            List<Integer> list
    ) {
        // код тут
    }
}

Спойлеры к решению

Подсказки

💡 Уникальный элемент можно использовать как ключ Map.
💡 Значением будет количество его появлений в списке.
💡 Для обновления счётчика удобно использовать merge() или getOrDefault().
💡 Через Stream API можно применить groupingBy() и counting() или summingInt().
💡 Для пустого списка нужно вернуть пустую карту.

Решение

Вариант через цикл:

public Map<Integer, Integer> countElementItems(
        List<Integer> list
) {
    if (list == null || list.isEmpty()) {
        return new HashMap<>();
    }

    Map<Integer, Integer> result = new HashMap<>();

    for (Integer value : list) {
        result.merge(value, 1, Integer::sum);
    }

    return result;
}

Вариант через Stream API:

public Map<Integer, Integer> countElementItems(
        List<Integer> list
) {
    if (list == null || list.isEmpty()) {
        return new HashMap<>();
    }

    return list.stream()
            .collect(Collectors.groupingBy(
                    value -> value,
                    Collectors.summingInt(value -> 1)
            ));
}

Ключами карты являются уникальные элементы списка, а значениями — количество их вхождений.

Для сохранения порядка первого появления элементов можно использовать LinkedHashMap:

return list.stream()
        .collect(Collectors.groupingBy(
                value -> value,
                LinkedHashMap::new,
                Collectors.summingInt(value -> 1)
        ));

Временная сложность — O(n), дополнительная память — O(k), где k — количество уникальных элементов.