Немного древней алгоритмической магии, или Решение интригующей последовательности задач из LeetCode

Некоторое время назад на сайте leetcode.com я наткнулся на забавную серию задач. Сами задачи не слишком сложны, но их решения довольно интригуют. Более того, проблемы такого типа часто возникают на собеседованиях в крупных компаниях, и понимание методов их решения может оказаться весьма полезным.

Первое задание — 136. Одиночное число (легкое)

Учитывая непустой массив целых чисел, в котором каждый элемент встречается дважды, кроме одного, вам нужно найти элемент без пары. Решите задачу за время O(n) и с постоянным объемом дополнительной памяти.

Пример 1:

Ввод: числа = [1, 3, 3, 2, 6, 2, 1]

Выход: 6

Пример 2:

Ввод: числа = [12, 1, 1, 7, 1, 12, 1]

Выход: 7

Пример 3:

Ввод: числа = [6]

Выход: 6

Мы воспользуемся свойством функции XOR, которая возвращает 1 только в том случае, если ее операнды различны. Проходя по всем элементам массива и выполняя над ними побитовое исключающее ИЛИ, мы обнуляем все одинаковые битовые значения. В результате останется желаемый результат.

Вот краткий код решения Python3:

 def single_number(nums: list) -> int: result = 0 for el in nums: result ^= el return result

Мы используем ровно столько дополнительной памяти, сколько занимает целое число, и находим решение за один проход по заданному массиву, что дает нам сложность O(n). Это лаконичное и элегантное решение.

Вторая задача — 137. Одиночное число II (средняя сложность).

Учитывая непустой массив целых чисел, в котором каждый элемент встречается три раза, кроме одного, и только один элемент появляется один раз, нам нужно найти этот уникальный элемент. Решите задачу за время O(n) и с постоянным объемом дополнительной памяти.

Пример 1:

Ввод: числа = [3, 1, 3, 3]

Выход: 1

Пример 2:

Ввод: числа = [12, 1, 1, 5, 1, 12, 12]

Выход: 5

Пример 3:

Ввод: числа = [6]

Выход: 6

К сожалению, в данном случае мы не можем использовать предыдущий трюк, так как не можем превратить парные биты в нужной позиции в нули. Было бы заманчиво преобразовать данный массив в формат предыдущей задачи, а затем решить его аналогичным образом.

Рассуждая таким образом, легко заметить, что если бы мы знали, что уже дважды (или трижды) встречали число N при обходе массива, мы могли бы добавить к получаемой сумме дополнительное исключающее ИЛИ с N. Это сделает окончательный результат XOR с этим числом четным, тем самым исключив его из окончательной суммы, и то, что останется, будет нашим ответом.

 def single_number_ii(nums: list) -> int: mem = {} result = 0 for el in nums: if not mem.get(el, False): mem[el] = 1 else: mem[el] += 1 if mem[el] == 2: result ^= el result ^= el return result

К сожалению, это решение потребует максимум (len(nums)-1)/3 с точки зрения памяти, что нельзя считать постоянным потреблением, поэтому нам придется искать другое решение.

Давайте попробуем изменить наш подход.

Ранее мы использовали XOR (который представляет собой сложение по модулю 2). Если бы мы реализовали сложение по модулю 3, мы могли бы легко применить трюк из предыдущего примера.

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

Итак, давайте применим еще немного побитовой магии:

 def single_number_137_ii(nums: list) -> int: ans, acc = 0, 0 for n in nums: ans = ans ^ n & ~acc acc = acc ^ n & ~ans return ans

Таким образом, все тройные числа обнуляются, и у нас остается только то число, которое встречается только один раз.

Третье задание — 260. Одиночное число III (средняя сложность).

Учитывая непустой массив целых чисел, в котором каждый элемент появляется дважды, за исключением двух элементов, которые появляются только один раз, нам нужно найти эти уникальные элементы. Цель состоит в том, чтобы решить задачу за время O(n) и с постоянной дополнительной памятью, причем порядок уникальных элементов не имеет значения.

Пример 1:

Ввод: числа = [1, 2, 1, 3, 2, 5]

Выход: [3, 5]

Пример 2:

Ввод: числа = [1, -2]

Выход: [-2, 1]

Очевидно, что мы можем легко исключить все парные числа с помощью операции XOR, как мы это делали при решении первой задачи. Сложность задачи заключается в том, чтобы идентифицировать любое из уникальных чисел, после чего второе можно легко вычислить, выполняя операцию XOR с нашей суммой XOR.

Чтобы добиться этого, нам просто нужно найти любой бит, отличающийся между этими уникальными числами. Затем снова перебираем массив, выполняя XOR-суммирование и разделяя результаты на две группы — для чисел, где этот бит установлен, и для тех, где он равен 0. В результате получаем искомые уникальные элементы.

 def single_number_260(nums: list) -> int: res1, res2 = 0, 0 glob_xor = 0 for n in nums: glob_xor ^= n diff_bit = glob_xor & ~(glob_xor - 1) for n in nums: if n & diff_bit: res1 ^= n else: res2 ^= n return [res1, res2]

Несмотря на необходимость дважды перебирать массив, сложность остается O(n), а потребление памяти составляет всего 2 целых числа.

NB: Несмотря на то, что int в Python не совсем такой же, как int в других языках, мы будем считать его размер константой.