Поиск первого неповторяющегося элемента в массиве

21. Найти первый неповторяющийся элемент в массиве

Условие задачи:
Дан массив целых чисел.

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

Код:

public class Main {
    public static void main(String[] args) {
        int[] array = {9, 4, 9, 6, 6, 4, 5};
        // TODO
    }
}

Пример 1:

Вход:  [9, 4, 9, 6, 6, 4, 5]
Выход: 5

Пример 2:

Вход:  [1, 2, 3, 2, 1]
Выход: 3

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

Подсказки

💡 Сначала подсчитай количество вхождений каждого числа.
💡 Для этого удобно использовать HashMap<Integer, Integer>.
💡 Затем ещё раз пройди по исходному массиву слева направо.
💡 Первый элемент с частотой 1 и будет ответом.

Решение

public static OptionalInt findFirstUnique(int[] array) {
    Map<Integer, Integer> frequencies = new HashMap<>();

    for (int value : array) {
        frequencies.merge(value, 1, Integer::sum);
    }

    for (int value : array) {
        if (frequencies.get(value) == 1) {
            return OptionalInt.of(value);
        }
    }

    return OptionalInt.empty();
}

Пример использования:

int[] array = {9, 4, 9, 6, 6, 4, 5};

findFirstUnique(array)
        .ifPresentOrElse(
                System.out::println,
                () -> System.out.println("Уникальных элементов нет")
        );

Результат:

На первом проходе подсчитывается частота каждого значения:

frequencies.merge(value, 1, Integer::sum);

После этого массив просматривается повторно в исходном порядке:

for (int value : array) {
    if (frequencies.get(value) == 1) {
        return OptionalInt.of(value);
    }
}

Именно второй проход гарантирует, что будет найден первый неповторяющийся элемент.

LinkedHashMap здесь не требуется, поскольку порядок элементов берётся непосредственно из исходного массива.

OptionalInt позволяет корректно обозначить отсутствие результата и не использовать специальное значение вроде -1, которое само может находиться в массиве.

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