240.搜索二维矩阵Ⅱ

240.搜索二维矩阵Ⅱ

240. 搜索二维矩阵 II 题解

题目

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

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

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

image-20231019231252838

思路

如果我们把矩阵旋转45度，就会发现变成了一个类似二叉树，在节点的右边的数都比节点大，左边的数都比节点小

这个时候，我们从左下或者右上进行比较，如果num<target那么列加一，往前走一列，如果num>target那么排减一

image-20231019231409554

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
  ******************************************************************************
  * @number         : 240
  * @title          : 搜索二维矩阵 II
  * @attention      : 数组、二分查找、分治、矩阵
  * @author         : zzzhou
  * @date           : 2023/10/19
  ******************************************************************************
  */


#include "vector"
#include  "bits/stdc++.h"

using namespace std;
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int rows=matrix.size(),cols=matrix[0].size();
        int start;
        int col=0,row=rows-1;
        while(col<cols && row>=0){
            start=matrix[row][col];
            if (start==target) return true;
            if (start>target)
                row--;
            else
                col++;
        }
    }
};

int main() {
    vector<vector<int>>arr={{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}};
    int target=5;
    Solution s;
    s.searchMatrix(arr,target);
    return 0;
}

结束

很巧妙…