Leetcode-240. 搜索二维矩阵 II

题目

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[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]], target = 5
输出：true

1.直接查找

我们直接遍历整个矩阵 matrix，判断 ttarget 是否出现即可。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row in matrix:
            for element in row:
                if element == target:
                    return True
        return False

时间复杂度分析：O(n2)

2.二分查找

由于矩阵 matrix 中每一行的元素都是升序排列的，因此我们可以对每一行都使用一次二分查找，判断 target 是否在该行中，从而判断 target 是否出现。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row in matrix:
            idx = bisect.bisect_left(row, target)
            if idx < len(row) and row[idx] == target:
                return True
        return False

时间复杂度分析：O(log2(n))

3.Z字查找

我们可以从矩阵 matrix 的右上角(0,n−1) 进行搜索。在每一步的搜索过程中，如果我们位于位置 (k,v)，

如果 matrix[k,v]=target，说明搜索完成；

如果 matrix[k,v]>target，由于每一列的元素都是升序排列的，那么在当前的搜索矩阵中，所有位于第 v列的元素都是严格大于 target 的，因此我们可以将它们全部忽略，即将 v减少 1；

如果 matrix[k,v]<target，由于每一行的元素都是升序排列的，那么在当前的搜索矩阵中，所有位于第 k行的元素都是严格小于 target 的，因此我们可以将它们全部忽略，即将 k增加 1。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m,n=len(matrix),len(matrix[0])
        k, v= 0,n-1
        while k<m and v>=0:
            if matrix[k][v] == target:
                return True
            elif matrix[k][v] > target:
                v-=1
            else:
                k+=1
        return False

时间复杂度分析：O(n)