03_搜索二维矩阵 Ⅱ （Python）

柔光的暖阳◎ 2023-01-13 05:54 81阅读 0赞

### 目录 ###

*  搜索二维矩阵 II
 *  示例 1：
 *  示例 2：
 *  提示：
 *  解答
 *   *  1，解法一 暴力
     *  2，解法二 右上
     *  3，解法三 左下

# 搜索二维矩阵 II #

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

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

# 示例 1： #

![img][]

> 输入：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

# 示例 2： #

![img][img 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 = 20  
> 输出：false

# 提示： #

m == matrix.length  
n == matrix\[i\].length  
1 <= n, m <= 300  
\-109 <= `matix[i][j]` <= 109  
每行的所有元素从左到右升序排列  
每列的所有元素从上到下升序排列  
\-109 <= target <= 109

# 解答 #

## 1，解法一 暴力 ##

暴力查找是最简单的，但效率不高，我们来看下代码。

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

## 2，解法二 右上 ##

这题说了，每行的元素从左到右升序排列。每列的元素从上到下升序排列。如果还是用暴力求解肯定是不明智的，我们可以从矩阵的**右上角**开始找，

1，如果找到就直接返回

2，如果没找到就继续查找

如果查找的值小于target就往下找  
如果查找的值大于target就往左找。

为什么从没看到过从左上角的呢>因为往右再往下的时候还得往左

class Solution:
        def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
            # 行数
            row = 0
            # 列数 由于从右上角开始 所以列数字为len-1
            col = len(matrix[0])-1
            while(row<=len(matrix)-1 and col>=0):
                if(matrix[row][col]==target):
                    return True
                elif (matrix[row][col]<target):
                    row+=1
                elif (matrix[row][col]>target):
                    col-=1
            return False

## 3，解法三 左下 ##

除了从矩阵的右上角开始找，我们还可以从矩阵的左下角开始找，这两个都是可以的。 一模一样滴

那么能不能从左上角或者右下角开始找呢，这个比较麻烦。假如从左上角开始找，当查找的值num小于target的时候，我们下一步肯定是要找比num大的值，如果还找比他小的就没有意义了。但问题是无论你从右边还是下边找，都是大于num的，怎么确定该往哪个方向找呢，这个就不好判断了。

class Solution:
        def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
            # 行数
            row = len(matrix)-1
            # 列数
            col = 0
            while(row>=0 and col<=len(matrix[0])-1):
                if(matrix[row][col]==target):
                    return True
                elif (matrix[row][col]<target):
                    col+=1
                elif (matrix[row][col]>target):
                    row-=1
            return False

[img]: /images/20221022/3ad451f054ff40f491937a4d42b74b10.png
[img 1]: /images/20221022/418380354d0149089e3d50c32567b546.png