class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m = len(matrix)
        n = len(matrix[0])
        is_zero = []
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    is_zero.append([i, j])
        
        for i, j in is_zero:
            ii = 0
            while 0 <= ii <= m-1:
                matrix[ii][j] = 0
                ii += 1
            jj = 0
            while 0 <= jj <= n-1:
                matrix[i][jj] = 0
                jj+= 1

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        ans = []
        while matrix:
            ans.extend(matrix[0])
            matrix.pop(0)
            matrix = list(zip(*matrix))[::-1]
        
        return ans

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        # Python 这里不能 matrix_new = matrix 或 matrix_new = matrix[:] 因为是引用拷贝
        matrix_new = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                matrix_new[j][n - i - 1] = matrix[i][j]
        # 不能写成 matrix = matrix_new
        matrix[:] = matrix_new

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        
        def search(i, j, target):
            up, down = 0, i
            while up <= down:
                mid = (up + down) / 2
                mid = int(mid)
                if matrix[mid][j] == target:
                    return True
                elif matrix[mid][j] > target:
                    # 1
                    down = mid - 1
                elif matrix[mid][j] < target:
                    up = mid + 1

        i, j =0, 0
        queue = []
        m = len(matrix)
        n = len(matrix[0])
        for j in range(n-1, -1, -1):
            if matrix[0][j] < target:
                if search(m-1, j, target):
                    return True
            elif matrix[0][j] == target:
                return True