当前位置：首页 > news >正文

2023-08-07力扣今日六题-不错题

news 2025/8/24 3:22:28

链接：

剑指 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;
}

限制：