2023-08-07力扣今日六题-不错题-Toy模板网

这篇具有很好参考价值的文章主要介绍了2023-08-07力扣今日六题-不错题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

链接：

剑指 Offer 04. 二维数组中的查找

题意：

一个二维矩阵数组，在行上非递减，列上也非递减

解：

虽然在行列上非递减，但是整体并不有序，第一行存在大于第二行的数字，第一列存在大于第二列的数字，所有非递减只对单行单列有效

如果从左上角开始遍历，就会发现往下走和往右走都是数值变大，同时两种走法不存在优先级，只能做到优化的O(N^2)遍历

但是如果从右上角开始遍历，就能发现往下走和往左走分别是数值变大和数值变小，以此进行类似二分查找的过程

实际代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target)
{
    int lgrow=matrix.size(); if(!lgrow) return false;
    int lgcol=matrix[0].size(); if(!lgcol) return false;
    
    PII start(lgrow-1,0);
    while(true)
    {
        if(matrix[start.first][start.second]==target) return true;
        if(matrix[start.first][start.second]<target)
        {
            start.second++;
            if(start.second>=lgcol) return false;
        }
        else
        {
            start.first--;
            if(start.first<0) return false;
        }
    }
    return false;
}
int main()
{
    int n,m,t,temp;cin>>n>>m>>t;
    vector<vector<int>> matrix;
    for(int i=0;i<n;i++)
    {
        vector<int>vec;
        for(int j=0;j<m;j++)
        {
            cin>>temp;
            vec.push_back(temp);
        }
        matrix.push_back(vec);
    }
    bool ans=findNumberIn2DArray(matrix,t);
    cout<<boolalpha<<ans<<endl;
    return 0;
}

限制：文章来源地址https://www.toymoban.com/news/detail-633379.html