Python程式：在二進位制矩陣中找到最左側1所在的列索引？

假設我們有一個二維二進位制矩陣。每一行都是按升序排序的，0在1之前，我們需要找到值為1的最左側列索引。如果沒有這樣的結果，則返回-1。

所以，如果輸入是這樣的

那麼輸出將是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

Arnab Chakraborty

更新於: 2020年11月10日

210 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習