arrays - 在按行排序的矩阵中找到表示最小整数的行

Question

我在最近的一次 Java 电话面试中被问到这个问题:

给定一个具有以下属性的 NxN 二进制 (0-1) 矩阵:

• 对每一行进行排序(0 的序列后跟 1 的序列)
• 每一行代表一个无符号整数(通过读取位)
• 每一行都是独一无二的

例子:

0 1 1
1 1 1
0 0 1

每一行中的位值被排序，行代表整数3、7和1。

找到代表最小整数的行。在上面的例子中，答案是第 3 行，它代表整数 1。

我从二次复杂度的蛮力开始。面试官回答说我没有利用排序后的属性(property)。

经过深思熟虑，我对每一行都使用了二进制搜索，结果达到了 O(nlogn)。他问我是否可以进一步改进。想了很多都没有改进。

如果有人能就改进它提出任何建议，我将不胜感激。

另一个例子:

0 1 1 1
0 0 0 1
0 0 0 0
1 1 1 1

答案将在第 3 行，代表整数 0。

Answer 1

从第 1 行开始。向右走，直到您找到第一个 1。然后向下到第 2 行，但保持在同一列并重复向右移动的过程，直到您点击 1。反复这样做。您最后一步正确的那一行就是您的答案。

这是一个 O(N+M) 的解决方案(对于 NxM 矩阵，或 O(N) 对于问题中给出的 NxN 方矩阵)。

使用你的例子:

0 1 1 1
0 0 0 1
0 0 0 0
1 1 1 1

这里的.代表遍历的路径:

. . 1 1
0 . . .
0 0 0 . . Last right step, therefore this is our answer
1 1 1 1 .

此解决方案适用于非方矩阵，为 NxM 矩阵保留最坏情况下的 O(N+M) 效率。

为什么会这样？保证数字将被排序意味着每一行将是一系列 0，然后是一系列 1。因此，一行的大小等于您在击中 1 之前可以走多远。因此，如果一行可以通过仅跟随 0 使您走得更远，那么它一定比我们之前处理过的任何内容都长。

Python代码:

li = [[0, 1, 1, 1],
      [0, 0, 0, 1],
      [0, 0, 0, 0],
      [1, 1, 1, 1]]

ans, j = 0, 0
for i, row in enumerate(li):
  while j < len(row) and row[j] == 0:
    j += 1
    ans = i

print "Row", ans+1, "".join(map(str, li[ans]))

还有一个更简单的解决方案，因为总是有一个 NxN 方矩阵和不同的行在一起的限制。它们一起意味着具有最低值的行将是 0 0 ... 0 1 或 0 0 ... 0 0。这是因为矩阵中有 N+1 个可能的数字，所以“缺失”的数字要么是 0(在这种情况下，代表的最小值是 1)，要么是其他数字(最小值是 0)。

有了这些知识，我们检查从右边数第二列是否有 0。当我们找到一个时，我们向它的右边看，如果它包含另一个 0，我们就有了答案(只能有一行以 0)。否则，我们继续在该列中搜索另一个 0。如果没有找到另一个 0，则我们找到的第一个就是我们要查找的行(只能有一个以 01 结尾的行> 因为没有以 00 结尾的，所以这是最小的)。

Python代码:

li = [[0, 1, 1, 1],
      [0, 0, 0, 1],
      [0, 0, 0, 0],
      [1, 1, 1, 1]]

for i, row in enumerate(li):
  if row[-2] == 0:
    ans = i
    if row[-1] == 0:
      break

print "Row", ans+1, "".join(map(str, li[ans]))

该解决方案以 O(N) 的最小难度回答问题，但将其推广以处理非正方形 NxM 矩阵或非不同的数字将使其最坏情况下的效率达到 O(N^2)。我个人更喜欢第一种解决方案。