Найти недостающую строку в n * 2 ^ n матрице за 2 ^ n времени Алгоритм

Question

Я столкнулся с вопросом об алгоритмах, который поначалу казался простым, но я озадачен и не знаю, что делать! вопрос в следующем:

Предположим, у нас есть число n, а затем у нас есть матрица из n столбцов и 2 * n строк. это похоже на набор мощности (например, для n = 2 у нас есть 10,11,00,01). строки не обязательно следуют за любым порядком. также мы можем получить доступ к каждому члену матрицы за O (1) раз. теперь у нас есть (2 ^ n) -1 строк, и мы хотим найти последнюю строку за наименьшее возможное время (обратите внимание, что есть n * (2 ^ n-1) членов, и у нас есть только O (2 ^ н) время). Как мы можем это сделать? (у нас есть O (n) памяти. хотя я не уверен, достаточно ли этого. если вы знаете ответ, который использует какой-либо объем памяти, это нормально)

Пример ввода:

3
101
110
100
000
111
011
010

Пример вывода: 001

Я пытался смоделировать это с помощью популярной проблемы пропущенных битов (хранив элементы матрицы), но не смог добиться большого прогресса.

P.S. реализация алгоритма на C / C ++ / Java / Python будет очень цениться, поскольку она проясняет ситуацию.

P.S.S: Вы можете также привести некоторые источники? или расскажите, как вы пришли к ответу и как вы относитесь к таким вопросам?

Answer 1

У вас есть 2 дела здесь:

1. Вырожденный случай: N == 1, что очевидно. 0 -> 1 и 1 -> 0; Вы можете, скажем, поставить его как ~item

2. Общая информация Дело N > 1. Все, что вам нужно сделать, это xor все значения:

   101 ^ 110 ^ 100 ^ 000 ^ 111 ^ 011 ^ 010 == 001

алгоритм имеет O(N * 2**N) сложность по времени (мы должны прочитать каждую ячейку матрицы) и требует O(n) места (для хранения временной суммы при хоринге).

C # реализация ( Linq ):

  string source = "3 101 110 100 000 111 011 010";

  // "001"
  // new char[] { ' ', '\r', '\n', 't' } - to be on the safe side -
  // whatever delimiter is we'll get a correct array
  string result = source
    .Split(new char[] { ' ', '\r', '\n', 't' }, StringSplitOptions.RemoveEmptyEntries)
    .Skip(1) // we don't want "3"
    .Aggregate((sum, item) =>  // xoring strings
       string.Concat(sum.Zip(item, (x, y) => (char)((x - '0') ^ (y - '0') + '0'))));

Давайте докажем правильность алгоритма (N > 1).

Так как N > 1 и, следовательно, 2**N >= 4, тогда 2**(N - 1) - это некоторое четное значение . Давайте посмотрим на произвольный бит всех 2**N элементов серии power

 000...0...0
 000...0...1
  ...
 111.......0
 111...1...1
       ^
     - N/2 '0's (even) and N/2 '1' (even), xor == 0

мы находим, что у нас есть ровно N / 2 ноля и N / 2 единицы; xor всех этих битов равно 0 (поскольку N / 2 == 2**(N - 1) является некоторым четным значением). Если пропущена одна строка, например 0...1...1 у нас есть 2 возможностей:

1. Пропущенный бит - 1. Итак, у нас есть N / 2 нолей и N / 2 - 1 единиц; xor всех битов возвращает 1
2. Пропущенный бит равен 0. Итак, у нас есть N / 2 - 1 нуля и N / 2 - 1 единицы; xor всех битов возвращает 1

Поскольку ^ является побитовой операцией (значение j-го бита не зависит от значений i-го бита), и мы доказываем, что произвольный бит является правильным во всем значении тоже правильно.

Answer 2

Ограничения немного расплывчаты, но вы, вероятно, ищете что-то вроде этого:

• Проверьте первый элемент во всех 2 ^ n строках, чтобы определить первый элемент в отсутствующей строке. Либо 1, либо ноль будут начинать 2 ^ (n-1) строк, а другая опция будет начинать 2 ^ (n-1) -1 строк - элемент с меньшим счетом начинает отсутствующую строку.
• Проверьте второй элемент в строках 2 ^ (n-1) -1, которые начинаются с того же элемента, что и отсутствующая строка, чтобы найти второй элемент в отсутствующей строке.
• Продолжить поиск всех n предметов в пропущенной строке.

Если вы суммируете количество прочитанных элементов, вы получите 2 ^ n + 2 ^ (n-1) + 2 ^ (n-2) ... что меньше 2 ^ (n + 1) и, следовательно, в O (2 ^ п)