哪些网站可以做ppi,app推广赚钱,山西两学一做网站登录,开发app需要什么样的团队链接#xff1a;
剑指 Offer 04. 二维数组中的查找
题意#xff1a;
一个二维矩阵数组#xff0c;在行上非递减#xff0c;列上也非递减
解#xff1a;
虽然在行列上非递减#xff0c;但是整体并不有序#xff0c;第一行存在大于第二行的数字#xff0c;第一列存在…链接
剑指 Offer 04. 二维数组中的查找
题意
一个二维矩阵数组在行上非递减列上也非递减
解
虽然在行列上非递减但是整体并不有序第一行存在大于第二行的数字第一列存在大于第二列的数字所有非递减只对单行单列有效
如果从左上角开始遍历就会发现往下走和往右走都是数值变大同时两种走法不存在优先级只能做到优化的O(N^2)遍历
但是如果从右上角开始遍历就能发现往下走和往左走分别是数值变大和数值变小以此进行类似二分查找的过程
实际代码
#includebits/stdc.h
using namespace std;
typedef pairint,int PII;
bool findNumberIn2DArray(vectorvectorint matrix, int target)
{int lgrowmatrix.size(); if(!lgrow) return false;int lgcolmatrix[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.secondlgcol) return false;}else{start.first--;if(start.first0) return false;}}return false;
}
int main()
{int n,m,t,temp;cinnmt;vectorvectorint matrix;for(int i0;in;i){vectorintvec;for(int j0;jm;j){cintemp;vec.push_back(temp);}matrix.push_back(vec);}bool ansfindNumberIn2DArray(matrix,t);coutboolalphaansendl;return 0;
}限制
0 n 10000 m 1000
