LeetCode 240 搜索二维矩阵

短命女 2022-03-16 12:13 248阅读 0赞

题目：

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

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

**示例:**

现有矩阵 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`。

给定 target = `20`，返回 `false`。

解题思路：通过观察矩阵的数据可以发现：矩阵中最大的数在右下角，最小的数在左上角。所以，可以将target与矩阵的最后一列从上到下比较，如果target大于该值，则继续向下找，直到target的值小于该值，那么，应该在该值的左下方所构成的矩阵继续寻找。如果所有的值都小于target，那么就直接返回false。所以，可以采用递归的 方法。

python代码：

class Solution:
        def fb(self, matrix, i, j, target):
            if j < 0:
                return False
            while i < len(matrix):
                if matrix[i][j] == target:
                    return True
                
                elif matrix[i][j] > target:
                    break
                else:
                    i += 1
            if i == len(matrix):
                return False
            else:
                return Solution.fb(self, matrix, i, j - 1, target)
        def searchMatrix(self, matrix, target):
            """
            :type matrix: List[List[int]]
            :type target: int
            :rtype: bool
            """
            row = len(matrix)
            if row == 0:
                return False
            col = len(matrix[0])
            if col == 0:
                return False
            return Solution.fb(self, matrix, 0, col - 1, target)

![Image 1][]也可以采用非递归的方法：

#include<bits/stdc++.h>
    using namespace std;
    int n, m;
    int main(){
        cin >> n >> m;
        int target;
        vector<vector<int>> arr(n, vector<int>(m, 0));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cin >> arr[i][j];
            }
        }
        cin >> target;
        int i, j;
        i = 0;
        j = m - 1;
        while(i < n && j >= 0){
            if(arr[i][j] == target){
                cout << "true" << endl;
                return 0;
            }
            else if(arr[i][j] > target){
                j--;
            }
            else{
                i++;
            }
        }
        cout << "false" << endl;
        return 0;
    }

[Image 1]: