Поиск единственного числа

Question

Задача

Дан список numbers_list. Элементы этого списка — целые неотрицательные числа от 0 до 100. Список составлен так, что каждое число в нём (кроме одного) встречается дважды.

Что нужно сделать

Составьте и запрограммируйте алгоритм, который находит в списке numbers_list то единственное число, которое встречается в нём один раз.

Задачу нужно решить тремя способами. Вторым способом решить получилось, 1 и 3 совсем не понимаю как делать.

Способ №1. Наиболее очевидный способ — взять первый элемент numbers_list (с индексом нуль) и, пробежавшись по списку, найти его пару. Если пара не находится, то первый элемент и есть искомое единичное число. Если пара нашлась — нужно взять второй элемент и повторить всё сначала. И так до тех пор, пока не найдётся нужное число. Реализуйте этот алгоритм.

Способ № 3. С помощью XOR.

Помогите, пожалуйста.

Пример списка:

numbers_list = [0, 1, 3, 4, 7, 98, 3, 1, 98, 7, 16, 16, 4, 0, 42]

Answer 1

tio.run

a = [0, 1, 3, 4, 7, 98, 3, 1, 98, 7, 16, 16, 4, 0, 42]

from functools import reduce
from operator import xor
print(reduce(xor, a, 0))

for i,x in enumerate(a):
  for j,y in enumerate(a):
    if x == y and i != j:
      break
  else:
    print(x)
    break

Answer 2

Побитовое исключающее или всех элементов:

a = [0, 1, 3, 4, 7, 98, 3, 1, 98, 7, 16, 16, 4, 0, 42]
x = 0
for v in a:
    x ^= v
print(x)

Исключающее или на множестве:

a = [0, 1, 3, 4, 7, 98, 3, 1, 98, 7, 16, 16, 4, 0, 42]

s = set()
for v in a:
    s ^= {v} # добавить если v не было в s, иначе убрать
print(next(iter(s))) # печать первого и единственного элемента s

Так как для списка заявлен маленький диапазон неотрицательных чисел, можно сделать исключающее или на списке индексов:

a = [0, 1, 3, 4, 7, 98, 3, 1, 98, 7, 16, 16, 4, 0, 42]

f = [False] * (max(a, default=-1) + 1)
for v in a:
    f[v] = not f[v]

for i, f_i in enumerate(f):
    if f_i:
        print(i)
        break

Флаги можно хранить не в списке f, но в числе f, которое в Питоне является множеством битов:

a = [0, 1, 3, 4, 7, 98, 3, 1, 98, 7, 16, 16, 4, 0, 42]

f = 0
for v in a:
    f ^= 1 << v # инвертируем бит с номером v

print(f.bit_length() - 1) # номер старшего и единственного установленного бита

Список можно отсортировать и считать сколько одинаковых элементов подряд в нём есть:

a = [0, 1, 3, 4, 7, 98, 3, 1, 98, 7, 16, 16, 4, 0, 42]

prev_v = -1  # предыдущее значение
c = 0        # число одинаковых элементов подряд
for v in sorted(a):
    if v == prev_v:
        c += 1
        continue
    if c == 1:     # группа из одного элемента - то что мы ищем
        break
    c = 1          # начинаем новую группу
    prev_v = v
print(prev_v)

Прямой (и медленный) поиск уникального элемента:

a = [0, 1, 3, 4, 7, 98, 3, 1, 98, 7, 16, 16, 4, 0, 42]

for v in a:
    if a.count(v) == 1:
        print(v)
        break

P.S. Во всех примерах я избегал импорта пакетов. Если импортировать пакеты, добавится бесчисленное количество вариантов решения задачи.

БЛОГ НА HUSL

Поиск единственного числа

Задача

Ответы (2 шт):