Нахождение первого неповторяющегося числа в массиве

Условие

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

public static void main(String []args){
    int[] numbers = {9, 4, 9, 6, 7, 4, 5};
    }

Ответ

Первое число с одним вхождением — 6. Подсчитайте частоты в Map и выполните повторный проход исходного массива, чтобы сохранить понятие «первое».

static java.util.OptionalInt unique(int[] numbers) {
    var counts = new java.util.HashMap<Integer, Integer>();
    for (int number : numbers) counts.merge(number, 1, Integer::sum);
    for (int number : numbers)
        if (counts.get(number) == 1) return java.util.OptionalInt.of(number);
    return java.util.OptionalInt.empty();
}

Среднее время O(n), память O(k). Выбор первого элемента из HashMap не подходит, поскольку порядок обхода произвольный. OptionalInt однозначно выражает отсутствие решения, не занимая какое-либо значение int под специальный маркер.