74. Search a 2D Matrix

[chengchengxu15]

leetcode: https://leetcode.com/problems/search-a-2d-matrix/

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row.

[chengchengxu15]

Binary Search Time Complexity: O(log(n*m)) Space Complexity: O(1)

重点：如何把中间的那个数在matrix里面找到：

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        n = len(matrix)
        m = len(matrix[0])
        start = 0
        end = m*n -1

        while start <= end:
            mid = (start + end)//2
            y_position = mid//m
            x_position = mid%m
            mid_value = matrix[y_position][x_position]
            if target == mid_value:
                return True
            elif target < mid_value:
                end = mid -1
            else:
                start = mid +1

        return False

[chengchengxu15]

暴力解法1 Brute Force 两个for,
Time Complexity: O(m*n) Space Complexity: O(1)

暴力解法2 Brute Force 新建一个list，全部放进去之后再用Binary Search Time Complexity: O(mn) Space Complexity: O(mn)

[chengchengxu15]

solution 4 从右上角开始，如果比target小，往下移一格；如果比target大，往左移一格；如果相等，return True

Time Complexity: O(m+n) Space Complexity: O(1)