Задача с собеседования в Zomato

Задача с собеседования в Zomato Дан целочисленный массив nums, в котором ровно два элемента встречаются только один раз, а все остальные элементы встречаются ровно два раза. Найдите два элемента, которые появляются только один раз. Вы можете вернуть ответ в любом порядке. Вы должны написать алгоритм, который работает за линейное время и использует только константное дополнительное пространство. Пример 1: Input: nums = [1,2,1,3,2,5] Output: [3,5] Explanation: [5, 3] - также валидный ответ. Пример 2: Input: nums = [-1,0] Output: [-1,0] Пример 3: Input: nums = [0,1] Output: [1,0] Ограничения: 2 <= nums.length <= 3 * 10⁴ -2³¹ <= nums[i] <= 2³¹ - 1 Каждое число в nums встретится два раза, только два числа встретятся один раз. НАШ ЧАТ АЛГОРИТМИСТОВ Решение Более сложный вариант задачи на использование побитового оператора XOR (исключающего ИЛИ) , сравнивающего два бита: - если биты одинаковые -> 0 - если биты разные -> 1 Применяем XOR для "обнуления" всех чисел в массиве, которые встречаются два раза, используя свойства: a ^ a = 0 и a ^ 0 = a. Предварительная сортировка не требуется, так как a ^ b = b ^ a. - проходим по массиву nums, накапливая XOR всех эл-в. Таким образом, получим XOR = a ^ b, где a и b - искомые числа. Теперь у нас есть некоторое значение XOR, хранящееся в двоичном виде. Предлагаю разобрать подробнее на примере 1: после первого прохода XOR = 3 ^ 5 = 6. В двоичном виде это выглядит следующим образом: 3 = 0 1 1 5 = 1 0 1 6 = 1 1 0 Единицы находятся в тех разрядах, где биты у a и b различаются => можем использовать какой-либо из этих разрядов в качестве разделителя. Найдём самый младший единичный бит с помощью цикла while: Пока XOR & diff_bit равно нулю: - ищем единичный бит, перебирая битовые позиции справа налево с помощью переменной diff_bit, сдвигая единицу из младшего разряда в старший. На примере XOR = 6 (110): diff_bit = 1 (001): 110 & 001 = 0 diff_bit = 2 (010): 110 & 010 = 2 => нужный бит найден - второй разряд справа. Также для нахождения младшего единичного бита-разделителя можно было бы использовать формулу: diff_bit = xor & -xor (рекомендую почитать о «дополнительном коде»). Таким образом, зная разделяющий бит, можем использовать его для распределения чисел по двум группам. Проходим по массиву nums, проверяя для каждого числа: - если diff_bit & текущее число не равно нулю => у числа стоит 1 в том же разряде, что и у diff_bit; - иначе => стоит 0. Уникальные числа a и b различаются в выбранном бите, а значит, попадут в разные группы. Парные же числа, имея одинаковые биты, попадут в одну и ту же группу и «обнулятся» при операции XOR. В каждой группе останется одно искомое число. Выводим найденные числа в виде массива. Сложность O(n) - по времени (проходим двумя циклами по n элементам) O(1) - по памяти (храним целочисленные переменные xor, diff_bit, a, b) Код class Solution: def singleNumber(self, nums: List[int]) -> List[int]: xor = 0 for n in nums: xor ^= n diff_bit = 1 while not(xor & diff_bit): diff_bit = diff_bit << 1 a, b = 0, 0 for n in nums: if diff_bit & n: a = a ^ n else: b = b ^ n return [a, b] @algoses