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

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

Задача

Найти первый элемент в массиве, который встречается только один раз. Например, в массиве [1, 2, 2, 3, 3, 4] первый неповторяющийся элемент это 1.

Решение 1: Использование HashMap (лучший подход)

Алгоритм:

1. Проходим по массиву и считаем частоту каждого элемента
2. Снова проходим по массиву и возвращаем первый элемент с частотой 1

public class FirstUniqueElement {
    public static int findFirstUnique(int[] arr) {
        // Шаг 1: Считаем частоту элементов
        Map<Integer, Integer> frequency = new HashMap<>();
        for (int num : arr) {
            frequency.put(num, frequency.getOrDefault(num, 0) + 1);
        }
        
        // Шаг 2: Находим первый элемент с частотой 1
        for (int num : arr) {
            if (frequency.get(num) == 1) {
                return num;
            }
        }
        
        // Если не найдено
        throw new IllegalArgumentException("Нет неповторяющихся элементов");
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 3, 3, 4};
        System.out.println(findFirstUnique(arr));  // Вывод: 1
        
        int[] arr2 = {4, 7, 7, 7, 3, 3, 3, 10};
        System.out.println(findFirstUnique(arr2)); // Вывод: 4
    }
}

Сложность:

• Временная: O(n) — два прохода по массиву
• Пространственная: O(n) — для HashMap

Решение 2: Использование LinkedHashMap (сохраняет порядок)

Eсли нужно сохранить порядок элементов, используйте LinkedHashMap:

public static int findFirstUnique(int[] arr) {
    Map<Integer, Integer> frequency = new LinkedHashMap<>();
    for (int num : arr) {
        frequency.put(num, frequency.getOrDefault(num, 0) + 1);
    }
    
    // LinkedHashMap сохраняет порядок вставки
    for (Map.Entry<Integer, Integer> entry : frequency.entrySet()) {
        if (entry.getValue() == 1) {
            return entry.getKey();
        }
    }
    
    throw new IllegalArgumentException("Нет неповторяющихся элементов");
}

Решение 3: Для массива символов

Частый вариант задачи — найти первый неповторяющийся символ в строке:

public static Character findFirstUniqueChar(String s) {
    Map<Character, Integer> frequency = new HashMap<>();
    
    // Считаем частоту символов
    for (char c : s.toCharArray()) {
        frequency.put(c, frequency.getOrDefault(c, 0) + 1);
    }
    
    // Находим первый уникальный
    for (char c : s.toCharArray()) {
        if (frequency.get(c) == 1) {
            return c;
        }
    }
    
    return null;  // Нет уникальных символов
}

public static void main(String[] args) {
    String s = "leetcode";
    System.out.println(findFirstUniqueChar(s));  // Вывод: l
    
    String s2 = "loveleetcode";
    System.out.println(findFirstUniqueChar(s2)); // Вывод: v
}

Решение 4: Оптимизация для символов (ASCII)

Для символов можно использовать массив вместо HashMap:

public static int findFirstUniqueChar(String s) {
    // Массив для частоты (для ASCII символов)
    int[] freq = new int[256];
    
    // Считаем частоту
    for (char c : s.toCharArray()) {
        freq[c]++;
    }
    
    // Находим первый уникальный
    for (int i = 0; i < s.length(); i++) {
        if (freq[s.charAt(i)] == 1) {
            return i;  // Возвращаем индекс
        }
    }
    
    return -1;  // Не найдено
}

Сложность:

• Временная: O(n)
• Пространственная: O(1) — фиксированный размер массива (256)

Это быстрее HashMap для небольших наборов символов.

Решение 5: Использование Stream API (Java 8+)

public static int findFirstUnique(int[] arr) {
    Map<Integer, Integer> frequency = new HashMap<>();
    for (int num : arr) {
        frequency.put(num, frequency.getOrDefault(num, 0) + 1);
    }
    
    return Arrays.stream(arr)
        .filter(num -> frequency.get(num) == 1)
        .findFirst()
        .orElseThrow(() -> new IllegalArgumentException("Нет уникальных элементов"));
}

Решение 6: Для потока данных (вариант с ограниченной памятью)

Если массив огромный, можно использовать несколько проходов:

public static int findFirstUnique(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        boolean unique = true;
        for (int j = 0; j < arr.length; j++) {
            if (i != j && arr[i] == arr[j]) {
                unique = false;
                break;
            }
        }
        if (unique) {
            return arr[i];
        }
    }
    throw new IllegalArgumentException("Нет уникальных элементов");
}

Сложность:

• Временная: O(n²) — неэффективно для больших массивов
• Пространственная: O(1) — без дополнительной памяти

Этот подход используется редко, только если память критична.

Сравнение подходов

Полный пример с тестами

public class FirstUniqueFinder {
    public static int findFirstUnique(int[] arr) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("Пустой или null массив");
        }
        
        Map<Integer, Integer> frequency = new HashMap<>();
        for (int num : arr) {
            frequency.put(num, frequency.getOrDefault(num, 0) + 1);
        }
        
        for (int num : arr) {
            if (frequency.get(num) == 1) {
                return num;
            }
        }
        
        throw new IllegalArgumentException("Нет неповторяющихся элементов");
    }
    
    public static void main(String[] args) {
        // Тест 1
        assert findFirstUnique(new int[]{1, 2, 2, 3, 3, 4}) == 1;
        System.out.println("Тест 1 пройден");
        
        // Тест 2
        assert findFirstUnique(new int[]{5}) == 5;
        System.out.println("Тест 2 пройден");
        
        // Тест 3
        assert findFirstUnique(new int[]{1, 1, 2, 2, 3}) == 3;
        System.out.println("Тест 3 пройден");
        
        System.out.println("Все тесты пройдены!");
    }
}

Рекомендации

1. Для чисел/объектов: используйте HashMap — O(n) время, простой код
2. Для символов ASCII: используйте массив int[256] — O(n) время, O(1) память
3. Для символов Unicode: используйте LinkedHashMap или HashMap
4. Для больших наборов: рассмотрите Stream API для читаемости
5. Обработайте исключения: проверяйте пустой массив и случай без уникальных элементов