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

从第1行开始。继续前进，直到第一个1。然后跳至第2行，但仍留在同一列中，重复右移的过程，直到您点击为止1。重复执行此操作。您上一步右移的行就是您的答案。

这是一个O（N + M）解（对于NxM矩阵，或者对于正方形NxN矩阵为O（N），如问题所示）。

使用您的示例：

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个可能的数字中的N个，因此“缺失”数字要么为0（在这种情况下，表示的最小值为1），要么为其他数值（最小值为0）。

掌握了这些知识之后，我们从右边第二列开始检查是否为0。找到一个时，我们向右看，如果包含另一个0，我们得到答案（只能有一行以a结尾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）。我个人更喜欢第一个解决方案。