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

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

Условие задачи:

Дан массив целых чисел.

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

Если такого элемента нет, нужно предусмотреть соответствующую обработку.

Исходный код:

public class Main {

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

        int n = ...
    }
}

Для указанного массива первый неповторяющийся элемент — 6.

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

Подсказки

💡 Сначала можно посчитать, сколько раз встречается каждый элемент массива.

💡 Для хранения количества вхождений удобно использовать Map<Integer, Integer>.

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

Решение

Для решения задачи используем HashMap, где ключом будет значение из массива, а значением — количество его вхождений.

На первом проходе посчитаем частоту каждого числа.

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

import java.util.HashMap;
import java.util.Map;

public class Main {

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

        Integer n = findFirstUnique(arr);

        System.out.println(n);
    }

    public static Integer findFirstUnique(int[] arr) {
        Map<Integer, Integer> occurrences = new HashMap<>();

        for (int value : arr) {
            occurrences.put(
                    value,
                    occurrences.getOrDefault(value, 0) + 1
            );
        }

        for (int value : arr) {
            if (occurrences.get(value) == 1) {
                return value;
            }
        }

        return null;
    }
}

Результат:

Почему требуется два прохода?

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

Поэтому второй проход выполняется непосредственно по arr.

Для массива:

[9, 4, 9, 6, 7, 4, 5]

частоты будут следующими:

Первым элементом массива, частота которого равна 1, является 6.

Сложность:

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