один элемент в списке

Question

Я довольно новичок в python и наткнулся на этот код, чтобы найти один элемент в списке

Вот код:

def single_number(arr):
    ones, twos = 0, 0
    for x in arr:
        ones, twos = (ones ^ x) & ~twos, (ones & x) | (twos & ~x)
    assert twos == 0
    return ones
arr1 = [5, 3, 4, 3, 5, 5, 3]
print(single_number(arr1))

Я просто не могу понять, что делает линия

ones, twos = (ones ^ x) & ~twos, (ones & x) | (twos & ~x)
assert twos==0

Answer 1

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

Проще понять, если мы хотим выбрать одно значение из массива, содержащего пары вместо троек. Тогда мы могли бы просто сделать ...

ones = ones ^ x

... потому что у ^ х ^ х == у. Таким образом, все пары отменяются, и у вас остается одно значение.

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

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

Answer 2

Вы не хотели бы делать это так, если только вы не действительно ограничены в объеме памяти - и даже тогда вам, вероятно, не следует его использовать.

Это своего рода "магия" сдвига битов / битовых операций, которая

• не интуитивна
• опасна для скрипки с
• плохо для поддержания
• трудный для понимания

Счетчик работает в O (n) - это лучшее, что вы можете сделать, чтобы проверить все элементы в списке - это просто займет немного больше постоянного времени(для установки объекта Counter) и некоторый пробел (для поддержания внутреннего диктата) над этой вещью с битовой сменой, которую вы нашли.

def getSingle(arr):
    from collections import Counter
    c = Counter(arr)

    return c.most_common()[-1]  # return the least common one -> (key,amounts) tuple

arr1 = [5, 3, 4, 3, 5, 5, 3]

counter = getSingle(arr1)

print (f"{counter[0]} occured {counter[1]} time(s)")

Вывод:

4 occured 1 time(s)