Task Livecoding Java Single Number | IT Ментор

96. Найти число, которое встречается один раз #

Условие задачи:
📌 Дан массив int[] nums, где каждое значение встречается ровно 2 раза, кроме одного — оно встречается 1 раз.
Нужно найти это значение. Можно начать с неоптимальных вариантов и перейти к оптимальным.

Код:

// Пример:
int[] nums = {4, 1, 2, 1, 2};
// Ответ: 4

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

Подсказки

💡 Неоптимально: посчитать частоты через Map.
💡 Лучше по памяти: отсортировать и пройти парами.
💡 Оптимально: использовать XOR — одинаковые числа взаимно уничтожатся (a ^ a = 0), а 0 ^ x = x.

Решение

Вариант 1 — через Map (O(n) по времени, O(n) по памяти)

public int singleNumberMap(int[] nums) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) {
        freq.merge(n, 1, Integer::sum);
    }
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        if (e.getValue() == 1) return e.getKey();
    }
    throw new IllegalArgumentException("No single element found");
}

Вариант 2 — сортировка (O(n log n) по времени, O(1..n) по памяти)

public int singleNumberSort(int[] nums) {
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 1; i += 2) {
        if (nums[i] != nums[i + 1]) {
            return nums[i];
        }
    }
    return nums[nums.length - 1];
}

Вариант 3 — XOR (O(n) по времени, O(1) по памяти) ✅ лучший

public int singleNumberXor(int[] nums) {
    int res = 0;
    for (int n : nums) {
        res ^= n;
    }
    return res;
}