Tìm kiếm trong ma trận 2D II (Search a 2D Matrix II) trong Python

Giả sử chúng ta có một ma trận m x n. Chúng ta phải viết thuật toán hiệu quả tìm kiếm một giá trị trong ma trận đó. Ma trận có các tính chất 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í dụ ma trận:

Nếu target là 5, trả về true; nếu target là 20, trả về false.

Để giải quyết, chúng ta làm theo các bước sau:

• len := số cột, c1 := 0, c2 := len - 1.

• Lặp vô hạn:

  • Nếu matrix[c1][c2] == target, trả về true.
  • Ngược lại nếu matrix[c1][c2] > target, thì c2 := c2 - 1, tiếp tục.
  • c1 := c1 + 1.
  • Nếu c1 >= số hàng hoặc c2 < 0, trả về false.

Ví dụ

class Solution:
    def searchMatrix(self, matrix, target):
        try:
            do_dai = len(matrix[0])
            cot_1, cot_2 = 0, do_dai - 1
            while True:
                if matrix[cot_1][cot_2] == target:
                    return True
                elif matrix[cot_1][cot_2] > target:
                    cot_2 -= 1
                    continue
                cot_1 = cot_1 + 1
                if cot_1 >= len(matrix) or cot_2 < 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