二维数组中的查找

题目链接:http://ac.jobdu.com/problem.php?pid=1384

思路:每次将要查找的数字t与二维数组右上角的元素比较。

1、t比右上角的元素大,那么t肯定比该元素所在行的所有元素都大,直接删除该行,更新右上角元素。

2、t比右上角的元素小,那么t肯定比该元素所在列的所有元素都小,直接删除该列,更新右上角元素。

3、t等于右上角的元素,直接返回"Yes"。

code:

 1 #include <cstdio>
 2 using namespace std;
 3 const int MAXN = 1005;
 4 int A[MAXN][MAXN];
 5 bool inArray(int m, int n, int t)
 6 {
 7     int i = 0;
 8     int j = n - 1;
 9     while (i < m && j >= 0)
10     {
11         if (A[i][j] > t) --j;
12         else if (A[i][j] < t) ++i;
13         else return true;
14     }
15     return false;
16 }
17  
18 int main()
19 {
20     int m, n, t;    // m:行数 n:列数 t:待查找的数字
21     while (scanf("%d %d %d", &m, &n, &t) != EOF)
22     {
23         // 输入数据
24         for (int i = 0; i < m; ++i)
25         {
26             for (int j = 0; j < n; ++j)
27             {
28                 scanf("%d", &A[i][j]);
29             }
30         }
31         // 预判
32         if (t < A[0][0] || t > A[m - 1][n - 1])
33         {
35             puts("No");
36             continue;
37         }
38         if (inArray(m, n, t)) puts("Yes");
39         else puts("No");
40     }
41     return 0;
42 }

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。