Как работает это решение Leetcode? (Нахождение одного числа в массиве) - PullRequest
Новая
       38

Как работает это решение Leetcode? (Нахождение одного числа в массиве)

0 голосов
/ 21 апреля 2020

Предыстория:

Итак, я впервые использовал leetcode и нашел простую проблему, которая показалась мне интересной, и решил ее. Я смотрел на представления других людей позже и нашел это и был поражен. У меня есть базовое понимание побитового оператора xor, но я действительно не понимаю, как работает это решение. Я был бы очень признателен за краткое изложение того, что происходит, потому что это кажется действительно интересным.

Проблема:

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

NOTE: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:
  Input: [2,2,1]
  Output: 1

Example 2:
  Input: [4,1,2,1,2]
  Output: 4

Решение: 

def single_number(list):
  result = 0
    for num in list:
      result ^= num
  return result

кредит mack0094 для этого решения

Ответы [ 3 ]

1 голос
/ 21 апреля 2020

Самым важным моментом здесь является оператор XOR, обозначаемый ^. Если мы напишем «result ^ = num», это также можно записать как «result = result ^ num»

Это решение работает, потому что мы гарантируем, что каждый элемент появляется дважды, кроме 1 из элементов.

Используя XOR, каждый раз, когда мы XOR числа дважды на один и тот же номер, мы получаем один и тот же исходный номер. Например: 4 ^ 1 = 5 и 5 ^ 1 = 4. Другой способ сказать это: 4 ^ 1 ^ 1 = 4.

Обратите внимание, что любое число XOR 0 является самим числом, пример: 0 ^ 5 = 5

Мы проведем oop через все элементы в списке. Давайте посмотрим, что произойдет с входными данными [2, 2, 1]: 

def single_number(list):
    result = 0
    for num in list:
      result ^= num
      print(result)
    return result

Оператор печати выдаст: 

2
0
1

Result starts as 0.
1st iteration: result = result ^ num = 0 ^ 2 = 2
2nd iteration: result = result ^ num = 2 ^ 2 = 0
3rd iteration: result = result ^ num = 0 ^ 1 = 1

Сначала вы должны получить XOR logi c , Затем убедите себя, что если число появится дважды, оно вернет одно число di git в исходную форму. Другой пример: 

[2, 3, 4, 3, 4]
2 ^ 3 = 1
1 ^ 4 = 5
5 ^ 3 = 6
6 ^ 4 = 2
0 голосов
/ 21 апреля 2020

Упрощенное объяснение

Если мы Xor будем указывать любое число идентичных чисел even, результат будет равен нулю. Пока есть одно значение, у которого нет идентичной пары, у нас будет значение, которое не равно 0.

Xor преобразуется в двоичный файл и сравнивает 2 бита. если биты одинаковы, результат равен 0, иначе 1. Выполнение этого создает новое число.

Ниже приведена таблица: 

  0111
^ 1010
======
  1101 = 13

Если мы сравним 2 числа совпадают, тогда результирующее число равно 0. Когда мы сравниваем число с 0, результирующее число является сравниваемым числом. 2 ^ 0 = 2. Потому что биты не выстраиваются. Поэтому список, составленный из следующих чисел, также будет работать [2,2,2,1,1,1,1] 1 отменяют себя, а первые 2 отменяют себя. Все, что осталось, это один 2. Надеюсь, что это имеет смысл.

0 голосов
/ 21 апреля 2020

Во-первых, у нас есть два факта об операторе xor:

  • x xor x = 0

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

, чтобы понять, почему алгоритм работает - сгруппируйте входную последовательность на пары.

например: мы можем написать пример входной последовательности как (a xor a) xor (b xor b) xor (c xor c) xor d. входная последовательность не имеет в этой форме, но мы всегда можем изменить ее порядок .

обратите внимание, что каждая пара оценивается как 0, и результат 0 xor d = d, который является числом, которое мы хотим найти.

...