Tìm kiếm Ma trận 2D II bằng Python

Giả sử chúng ta có một ma trận m x n. Chúng ta phải viết một thuật toán hiệu quả để tìm kiếm một giá trị trong ma trận đó. Ma trận này có các thuộc tính sau -

• Các số nguyên trong mỗi hàng được sắp xếp tăng dần từ trái sang phải.
• Các số nguyên trong mỗi cột được sắp xếp tăng dần từ trên xuống dưới.

Vì vậy, nếu ma trận giống như -

Nếu mục tiêu là 5 thì trả về true, nếu mục tiêu là 20 thì trả về false

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

• len:=số cột, c1:=0, c2:=len - 1
• trong khi đúng
  • nếu ma trận [c1, c2] =target, thì trả về true
  • else if ma trận [c1, c2]> target, then c2:=c2 - 1, continue
  • c1:=c1 + 1
  • nếu c1> =số hàng hoặc c2 <0, thì trả về false
  • trả về false

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

class Solution:
   def searchMatrix(self, matrix, target):
      try:
         length = len(matrix[0])
         counter1, counter2 = 0, length-1
         while True:
            if matrix[counter1][counter2] == target:
               return True
            elif matrix[counter1][counter2]>target:
               counter2-=1
               continue
            counter1 = counter1 + 1
            if counter1 >= len(matrix) or counter2<0:
               return False
         except:
            return False
ob1 = Solution()
print(ob1.searchMatrix([[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], 5))

Đầu vào

[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
5

Đầu ra

True