题目链接:Click
here~~
题意:
有一个特殊的二维数组 { a[n][m] },其每行和每列都是递增的。
如何查找出某一元素 x 是否存在于数组中。
解题思路:
每次考虑待查找矩阵右上角的元素 val 与 x 的关系。
若 val > x,则 val 所在列均 > x,从而可以使待查找矩阵缩小一列。
若 val < x,则 val 所在行均 < x,从而可以使待查找矩阵缩小一行。
复杂度 O(max(n,m))。
#include <stdio.h> #include <algorithm> using std::pair; using std::make_pair; const int N = 1e3 + 5; int a[N][N]; bool exist(int n,int m,int x) { pair<int,int> loc = make_pair(0,m-1); while(loc.first < n && loc.second >= 0) { int val = a[loc.first][loc.second]; if(val == x) return true; if(val > x) loc.second--; else loc.first++; } return false; } int main() { int n,m,x; while(~scanf("%d%d%d",&n,&m,&x)) { for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&a[i][j]); puts(exist(n,m,x)?"Yes":"No"); } return 0; }