Python程序：在二进制矩阵中找到最左侧1所在的列索引？

假设我们有一个二维二进制矩阵。每一行都是按升序排序的，0在1之前，我们需要找到值为1的最左侧列索引。如果没有这样的结果，则返回-1。

所以，如果输入是这样的

0001
0011
0011
0010

那么输出将是2，因为第二列在整个矩阵中具有最左侧的1。

要解决这个问题，我们将遵循以下步骤

  • 如果矩阵为空，则

    • 返回-1

  • N := 矩阵的行数

  • M := 矩阵的列数

  • i := 0, j := M - 1

  • leftmost := -1

  • 当 i < N 且 j >= 0 时，执行

    • 如果 matrix[i, j] 等于 0，则

      • i := i + 1

    • 否则，

      • leftmost := j

      • j := j - 1

  • 返回 leftmost


示例

 实时演示

class Solution:
   def solve(self, matrix):
      if not matrix or not matrix[0]:
         return -1

      N = len(matrix)
      M = len(matrix[0])

      i = 0
      j = M - 1

      leftmost = -1

      while i < N and j >= 0:
         if matrix[i][j] == 0:
            i += 1
         else:
            leftmost = j
            j -= 1

      return leftmost

ob = Solution()
matrix = [
   [0, 0, 0, 1],
   [0, 0, 1, 1],
   [0, 0, 1, 1],
   [0, 0, 1, 0]
]
print(ob.solve(matrix))

输入

[
[0, 0, 0, 1],
[0, 0, 1, 1],
[0, 0, 1, 1],
[0, 0, 1, 0] ]

输出

2

更新于: 2020年11月10日

210 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告