Исходная постановка задачи - это:
Учитывая массив из 32-битных целых без знака, в которых каждое число отображается ровно дважды, за исключением трех из них (которые появляются ровно один раз), найдите эти три числа в O (n), используя O (1) дополнительное пространство. Входной массив доступен только для чтения. Что делать, если есть k исключений вместо 3?
Легко решить это в Ο(1) времени и Ο(1) пространстве, если вы принимаете очень высокий постоянный коэффициент из-за ограничения ввода (массив может иметь не более 2 33 записей):
for i in lst:
if sum(1 for j in lst if i == j) == 1:
print i
Итак, для этого вопроса давайте отбросить ограничение по длине бит и сконцентрироваться на более общей проблеме, где числа могут иметь до m бит.
Обобщая алгоритм для k = 2, я имел в виду следующее:
- XOR эти числа с наименьшим значащим разрядом
1и те, у которых0отдельно. Если для обоих разделов результирующее значение не равно нулю, мы знаем, что мы разделили неповторяющиеся числа на две группы, каждая из которых имеет хотя бы один член - Для каждой из этих групп попробуйте разбить его дальше, исследуя второй-младший бит и т.д.
Однако есть особый случай, который следует учитывать. Если после разбиения группы значения XOR одной из групп равны нулю, мы не знаем, является ли одна из результирующих подгрупп пустой или нет. В этом случае мой алгоритм просто покидает этот бит и продолжает следующий, что неверно, например, он терпит неудачу для ввода [0,1,2,3,4,5,6].
Теперь идея состояла в том, чтобы вычислить не только XOR элемента, но и XOR значений после применения некоторой функции (здесь я выбрал f(x) = 3x + 1). См. Нижеприведенный ответ Евгения для встречного примера для этой дополнительной проверки.
Теперь, хотя приведенный ниже алгоритм не подходит для k >= 7, я по-прежнему включаю реализацию здесь, чтобы дать вам представление:
def xor(seq):
return reduce(lambda x, y: x ^ y, seq, 0)
def compute_xors(ary, mask, bits):
a = xor(i for i in ary if i & mask == bits)
b = xor(i * 3 + 1 for i in ary if i & mask == bits)
return a if max(a, b) > 0 else None
def solve(ary, high = 0, mask = 0, bits = 0, old_xor = 0):
for h in xrange(high, 32):
hibit = 1 << h
m = mask | hibit
# partition the array into two groups
x = compute_xors(ary, m, bits | hibit)
y = compute_xors(ary, m, bits)
if x is None or y is None:
# at this point, we can't be sure if both groups are non-empty,
# so we check the next bit
continue
mask |= hibit
# we recurse if we are absolutely sure that we can find at least one
# new value in both branches. This means that the number of recursions
# is linear in k, rather then exponential.
solve(ary, h + 1, mask, bits | hibit, x)
solve(ary, h + 1, mask, bits, y)
break
else:
# we couldn't find a partitioning bit, so we output (but
# this might be incorrect, see above!)
print old_xor
# expects input of the form "10 1 1 2 3 4 2 5 6 7 10"
ary = map(int, raw_input().split())
solve(ary, old_xor=xor(ary))
Из моего анализа этот код имеет худшую временную сложность O(k * m² * n), где n - количество входных элементов (XORing - O(m) и не более k операции секционирования могут быть успешными) и пространства сложность O(m²) (поскольку m - максимальная глубина рекурсии, а временные числа могут быть длиной m).
Конечно, вопрос заключается в правильном и эффективном подходе с хорошей асимптотической средой выполнения (предположим, что k << n и m << n здесь для полноты), что также требует небольшого дополнительного пространства (например, подходы что сортировка ввода не будет принята, потому что для этого нам понадобится как минимум O(n) дополнительное пространство, так как мы не можем изменить вход!).
РЕДАКТИРОВАТЬ: Теперь, когда доказанный алгоритм окажется неправильным, было бы, конечно, приятно видеть, как это можно сделать правильным, возможно, сделав его немного менее эффективным. Космическая сложность должна быть в o(n*m) (т.е. Сублинейно в общем числе входных битов). Было бы хорошо принять k в качестве дополнительного ввода, если это облегчит задачу.
