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

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

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

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

Код:

public static void main(String[] args) {
    int[] nums = {4, 5, 1, 2, 0, 4, 5, 2};
}

Для приведённого массива результат:

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

Подсказки

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

Решение

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

    for (int num : nums) {
        frequencies.merge(num, 1, Integer::sum);
    }

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

    return OptionalInt.empty();
}

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

public static void main(String[] args) {
    int[] nums = {4, 5, 1, 2, 0, 4, 5, 2};

    OptionalInt result = findFirstUnique(nums);

    result.ifPresent(System.out::println); // 1
}

На первом проходе:

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

подсчитывается количество появлений каждого числа.

Затем второй проход идёт в исходном порядке:

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

Поэтому возвращается именно первый неповторяющийся элемент.

Для массива:

[4, 5, 1, 2, 0, 4, 5, 2]

частоты будут:

Первым элементом с частотой 1 является 1.

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

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