Chương trình để tìm chỉ mục cột trong đó phần lớn nhất bên trái là 1 trong một ma trận nhị phân bằng Python?

Giả sử chúng ta có một ma trận nhị phân 2D. Ở đây, mỗi hàng được sắp xếp theo thứ tự tăng dần với các số 0 đứng trước 1s, chúng ta phải tìm chỉ mục cột ngoài cùng bên trái có giá trị là 1. Nếu không có kết quả như vậy, hãy trả về -1.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 2, vì cột thứ hai còn lại nhiều nhất là 1 trong toàn bộ ma trận.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• nếu ma trận trống, thì

  • trả về -1

• N:=số hàng của ma trận

• M:=số cột của ma trận

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

• ngoài cùng bên trái:=-1

• while i =0, do

  • nếu ma trận [i, j] giống 0 thì

    • i:=i + 1

  • nếu không,

    • ngoài cùng bên trái:=j

    • j:=j - 1

• quay lại ngoài cùng bên trái

Ví dụ

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))

Đầu vào

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

Đầu ra

2