Как найти первый неповторяющийся элемент в массиве

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

Базовое владение коллекциями: умеете ли вы получить O(n) вместо вложенных циклов и понимаете ли, какая Map сохраняет порядок. Следом просят оценить память, обойтись без второго прохода по массиву или обработать поток, который целиком не помещается.

Как отвечать

Наивный вариант со вложенным циклом даёт O(n²), его стоит назвать как отправную точку и сразу перейти к решению в два прохода. Первым считаете частоты в HashMap<Integer, Integer> через counts.merge(x, 1, Integer::sum), вторым идёте по исходному массиву и возвращаете первый элемент с частотой 1. Порядок берётся из массива, поэтому обычной HashMap достаточно. Время O(n), память O(k), где k это число различных значений.

Дальше полезно показать варианты:

• LinkedHashMap: хранит порядок вставки, и второй проход можно делать по карте, а не по массиву. Выгодно, когда различных значений намного меньше, чем элементов;
• массив счётчиков: если диапазон значений мал (символы ASCII, числа до тысячи), int[] count быстрее карты и обходится без упаковки в Integer;
• Stream API: groupingBy(Function.identity(), LinkedHashMap::new, counting()), затем фильтр по значению 1 и findFirst(). Коротко, но медленнее цикла из-за упаковки;
• поток данных: LinkedHashSet кандидатов плюс HashSet уже повторившихся. Повтор удаляет значение из кандидатов, и первый элемент набора в любой момент и есть ответ.

Отдельно договоритесь, что возвращать, если ответа нет. Значение -1 не годится, когда оно может встретиться в массиве; честнее OptionalInt или Optional<Integer>.

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

Ищут «первый» элемент обходом HashMap. Порядок итерации у неё не гарантирован, и тест на маленьких числах проходит случайно.

Сортируют массив, чтобы найти уникальные сравнением соседей. Уникальный элемент найдётся, но исходный порядок потерян, и ответ будет не первым, а наименьшим.

Возвращают null через Integer, а вызывающий код присваивает результат в int. Автораспаковка null даёт NullPointerException, и падает уже чужой метод. Рядом ещё одна ловушка: сравнение двух Integer через == работает только в кеше от -128 до 127.