0

Она находит единственное неспаренное число в массиве , объясните как она работает

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        x=0
        for i in nums:
            x^=i
        return x

1 ответ 1

0

^ — побитовая сумма по модулю 2 (XOR).

Вот её таблица истинности:

введите сюда описание изображения

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

a ^ a == 0
a ^ 0 == a

Поэтому для тех элементов, которые имеют пару, в результате получится ноль. Останется побитовая сумма по модулю 2 непарных элементов. Если такой элемент один в массиве, то он и получится.

4
  • а почему мы с i 'x^=i' это делаем?
    – dopefresh
    11 апр 2020 в 6:35
  • i — это очередной элемент списка. 11 апр 2020 в 6:55
  • А вы не знаете где найти подробную информацию по циклам for
    – dopefresh
    11 апр 2020 в 8:32
  • @dopefresh, ru.stackoverflow.com/a/420126/235436. Можете ещё поискать по запросу "python цикл for" в поисковой системе google. 11 апр 2020 в 8:45

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.