Chương trình tìm giá trị mục tiêu trong ma trận đã sắp xếp trong Python

Mô tả bài toán

Cho ma trận 2D, mỗi hàng và cột được sắp xếp không giảm. Kiểm tra xem giá trị target có tồn tại trong ma trận hay không.

Ví dụ: ma trận [[2,4,30],[3,4,31],[6,6,32]], target = 31 → True.

Giải thuật (Tìm kiếm từ góc trên phải)

1. Khởi tạo col = số cột - 1.
2. Duyệt từng hàng i:
   • Khi matrix[i][col] > target và col >= 0: giảm col.
   • Nếu matrix[i][col] == target: trả về True.
3. Trả về False.

Ví dụ mã Python

class Solution:
    def solve(self, matrix, target):
        col = len(matrix[0]) - 1
        for i in range(len(matrix)):
            while matrix[i][col] > target and col >= 0:
                col = col - 1
            if matrix[i][col] == target:
                return True
        return False

ob = Solution()
matrix = [[2, 4, 30], [3, 4, 31], [6, 6, 32]]
target = 31
print(ob.solve(matrix, target))

Đầu vào

matrix = [ [2, 4, 30], [3, 4, 31], [6, 6, 32]] target = 31

Đầu ra

True