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

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

Условие задачи:
Дан массив int[] nums, в котором каждое число встречается ровно два раза, кроме одного — оно встречается один раз.

Необходимо найти и вернуть это число.

Код:

int[] nums = {4, 1, 2, 1, 2};

// Ответ: 4

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

Подсказки

💡 Можно посчитать количество вхождений каждого числа через Map.
💡 Другой вариант — отсортировать массив и сравнивать элементы парами.
💡 Оптимальное решение использует XOR.
💡 Для XOR выполняются свойства: x ^ x = 0 и x ^ 0 = x.

Решение

Вариант через Map:

public int singleNumberMap(int[] nums) {
    Map<Integer, Integer> frequencies = new HashMap<>();

    for (int number : nums) {
        frequencies.merge(number, 1, Integer::sum);
    }

    for (Map.Entry<Integer, Integer> entry
            : frequencies.entrySet()) {
        if (entry.getValue() == 1) {
            return entry.getKey();
        }
    }

    throw new IllegalArgumentException(
            "Single number not found"
    );
}

Временная сложность — O(n), дополнительная память — O(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];
}

Временная сложность — O(n log n). Сортировка изменяет исходный массив.

Оптимальный вариант через XOR:

public int singleNumber(int[] nums) {
    int result = 0;

    for (int number : nums) {
        result ^= number;
    }

    return result;
}

Числа, встречающиеся дважды, взаимно уничтожаются:

4 ^ 1 ^ 2 ^ 1 ^ 2 = 4

Временная сложность — O(n), дополнительная память — O(1).