Как найти числа и количество их повторений в массиве чисел

Что проверяют

Знаете ли вы API коллекций и Stream API на уровне идиом, умеете ли назвать сложность и выбрать структуру под ограничения. Следом обычно меняют условие: нужен порядок первого появления, сортировка по частоте или решение без дополнительной памяти.

Как отвечать

Базовое решение за O(n) по времени и O(k) по памяти, где k число различных значений:

Map<Integer, Integer> counts = new HashMap<>();
for (int x : numbers) {
    counts.merge(x, 1, Integer::sum);
}

merge делает одну операцию вместо связки containsKey, get и put. Вариант с getOrDefault(x, 0) + 1 тоже нормален.

Потом покажите, что знаете альтернативы:

• Stream API: Arrays.stream(numbers).boxed().collect(Collectors.groupingBy(Function.identity(), Collectors.counting())). Для int[] нужен boxed(), а значения получатся типа Long;
• порядок: HashMap порядок не гарантирует. LinkedHashMap сохранит порядок первого появления, TreeMap отсортирует ключи. В groupingBy фабрику карты передают вторым аргументом, например TreeMap::new;
• малый диапазон значений: массив счётчиков вместо карты, индекс это значение со смещением. Без боксинга и хеширования, заметно быстрее;
• без дополнительной памяти: Arrays.sort и один проход с подсчётом подряд идущих одинаковых, O(n log n);
• только повторы: отфильтровать записи со счётчиком больше единицы.

Где спотыкаются

Пишут два вложенных цикла с флагом «уже посчитан». Это O(n²), и на миллионе элементов такое решение работает минутами.

Сравнивают счётчики типа Integer через ==. Кэш Integer.valueOf по умолчанию покрывает значения от -128 до 127, поэтому тест на маленьких числах проходит, а на реальных данных сравнение ломается. Нужен equals или распаковка в int.

Ожидают, что HashMap выведет числа по возрастанию. На маленьких целых так часто и выглядит, но это деталь реализации, а не контракт, и на других данных порядок поедет.