Определение первого уникального числа в массиве

Условие

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

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

Ответ

Сначала подсчитайте частоты, затем повторно пройдите массив в исходном порядке и верните первое число с частотой 1. Для примера это 6.

static java.util.OptionalInt firstUnique(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). OptionalInt отличает отсутствие результата от любого допустимого значения, включая -1 и 0. Нельзя выбирать первый элемент обхода HashMap: его порядок не соответствует порядку исходного массива.