Find Missing row in n*2^n matrix in 2^n time 算法题

Question

我遇到一道算法题，一开始看起来很简单，但我很困惑，不知道该怎么办！问题如下：

假设我们有一个数n，然后我们有一个n列2*n行的矩阵。它就像幂集（例如，对于 n=2，我们有 10,11,00,01）。这些行不一定遵循任何顺序。我们也可以在 O(1) 时间内访问每个矩阵成员。现在，我们有 (2^n)-1 行，我们想在尽可能短的时间内找到最后一行（请注意，有 n*(2^n-1) 个成员，而我们只有 O(2^ n）时间）。我们应该怎么做？（我们有 O(n) 内存。虽然我不确定它是否足够。如果你知道一个使用任意数量内存的答案，那很好）

示例输入：

示例输出：001

我尝试通过流行的缺失位问题（通过对矩阵成员进行异或运算）对其进行建模，但进展不大。

P.S。在 C/C++/Java/Python 上实现算法将非常受欢迎，因为它澄清了事情。

P.S.S：你能引用一些资料吗？或者告诉我你是如何得出答案的以及你是如何看待这些问题的？

Answer 1

约束有点模糊，但您可能正在寻找这样的东西：

检查所有 2^n 行中的第一项以确定缺失行中的第一项。 1 或 0 将开始 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^n)

Answer 2

您这里有 2 个案例：

退化案例：N == 1这是显而易见的。 0 -> 1 和 1 -> 0；你可以说，把它写成 ~item
一般案例N > 1。您所要做的就是 xor 所有值：

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

该算法具有 O(N * 2**N) 时间复杂度（我们必须读取矩阵的每个单元格）并且需要 O(n) space（在异或运算时存储时间和）。

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项的任意位

 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。所以我们有 N / 2 个零和 N / 2 - 1 个； xor 所有位 returns 1
遗漏的位是 0。所以我们有 N / 2 - 1 个零和 N / 2 - 1 个； xor 所有位 returns 1

因为^是一个位运算（第j位的值不依赖于第i位的值）并且我们证明任意位是正确的，整个值也是正确的。

Find Missing row in n*2^n matrix in 2^n time 算法题

Find Missing row in n*2^n matrix in 2^n time Algorithm question

algorithm

matrix

powerset