二维数组中的查找

浏览数：19 / 时间：2015年06月08日

题目链接：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 }