Найти k неповторяющихся -элементов в списке с «малым» дополнительным пространством

Исходная постановка задачи такова:

Given an array of 32bit unsigned integers in which every number appears exactly twice except three of them (which appear exactly once), find those three numbers in O(n) time using O(1) extra space. The input array is read-only. What if there are k exceptions instead of 3?

Это легко решить в Ο(1)времени и Ο(1)пространстве, если вы принимаете очень высокий постоянный коэффициент из-за входного ограничения (массив может иметь не более 2 ³³ записей):

for i in lst:
    if sum(1 for j in lst if i == j) == 1:
        print i

Итак, ради этого вопроса давайте отбросим ограничение на длину в битах и ​​сосредоточимся на более общей проблеме, когда числа могут иметь до mбит.

Обобщая алгоритм для k = 2 , я имел в виду следующее:

1. XOR для чисел с младшим битом 1и с 0отдельно. Если для обоих разбиений результирующее значение не равно нулю, мы знаем, что мы разбили неповторяющиеся -числа на две группы, каждая из которых имеет хотя бы одного члена
2. Для каждой из этих групп попытайтесь разбить ее дальше, проверив второй -младший значащий бит и так далее

. Однако следует рассмотреть частный случай. Если после разделения группы значения 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— количество входных элементов (XOR — это O(m)и не более kопераций разбиения могут быть успешными ). ] и пространственной сложностиO(m²)(потому что m— это максимальная глубина рекурсии, а временные числа могут иметь длинуm).

Вопрос, конечно, в том, существует ли правильный , эффективный подход с хорошим асимптотическим временем выполнения (давайте предположим, что k << nи m << nздесь для полноты ), что также требует небольшого дополнительное пространство (, например, подходы, при которых сортировка ввода не будет принята, потому что нам потребуется как минимум O(n)дополнительное пространство для этого, поскольку мы не можем изменить ввод! ).

РЕДАКТИРОВАТЬ:Теперь, когда вышеприведенный алгоритм оказался неверным, было бы, конечно, неплохо посмотреть, как его можно сделать правильным, возможно, сделав его немного менее эффективным. Пространственная сложность должна быть вo(n*m)(то есть сублинейный по общему количеству входных битов ). Было бы нормально взять kв качестве дополнительных входных данных, если это упростит задачу.