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

Условие

Задача: найти элемент массива целых чисел, который встречается только один раз, и вернуть первый такой элемент.

public class Main {
    public static void main(String[] args) {
        int[] numbers = {9, 4, 9, 6, 7, 4, 5};
        int result = firstUnique(numbers);
        System.out.println(result);
    }

    static int firstUnique(int[] numbers) {
        return -1;
    }
}

Ответ

Подсчитайте вхождения, затем пройдите массив ещё раз в исходном порядке. Для данного набора первым уникальным значением будет 6.

static int firstUnique(int[] numbers) {
    var counts = new java.util.HashMap<Integer, Integer>();
    for (int n : numbers) counts.merge(n, 1, Integer::sum);
    for (int n : numbers)
        if (counts.get(n) == 1) return n;
    throw new java.util.NoSuchElementException("No unique element");
}

Ожидаемое время O(n), память O(k). Для отсутствия результата выбран явный exception, поскольку сигнатура возвращает int и любой int, включая -1, может быть данными. Если контракт разрешено менять, OptionalInt позволяет выразить отсутствие без исключения.