Pythonのバイナリマトリックスで左端の1が存在する列インデックスを見つけるプログラム？

2Dバイナリ行列があるとします。ここでは、各行が昇順で並べ替えられ、0が1の前に来る場合、値が1の左端の列インデックスを見つける必要があります。そのような結果がない場合は、-1を返します。

したがって、入力が次のような場合

2番目の列がマトリックス全体でほとんど1を残しているため、出力は2になります。

これを解決するには、次の手順に従います。

• 行列が空の場合、

  • -1を返す

• N：=行列の行数

• M：=行列の列数

• i：=0、j：=M-1

• 左端：=-1

• i=0の場合、実行

  • matrix [i、j]が0と同じ場合、

    • i：=i + 1

  • それ以外の場合

    • 左端：=j

    • j：=j-1

• 左端に戻る

例

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