题目1384：二维数组中的查找
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：7318
解决：1418
- 题目描述：
-
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
- 输入：
-
输入可能包含多个测试样例，对于每个测试案例，
输入的第一行为两个整数m和n(1<=m,n<=1000)：代表将要输入的矩阵的行数和列数。
输入的第二行包括一个整数t(1<=t<=1000000)：代表要查找的数字。
接下来的m行，每行有n个数，代表题目所给出的m行n列的矩阵(矩阵如题目描述所示，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
- 输出：
-
对应每个测试案例，
输出”Yes”代表在二维数组中找到了数字t。
输出”No”代表在二维数组中没有找到数字t。
- 样例输入：
-
3 3 5 1 2 3 4 5 6 7 8 9 3 3 1 2 3 4 5 6 7 8 9 10 3 3 12 2 3 4 5 6 7 8 9 10
- 样例输出：
-
Yes No No
代码（一）：
题解：
1、找到所在位置所在行，通过和每一行最后一个元素比较
2、找到列中元素位置
#include <stdio.h>
#include <string.h>
int A[1010][1010];
void print(int flag){
if(flag == 2)
printf("Yes ");
else printf("No ");
}
int main(int argc, char const *argv[])
{
int m, n, mark, pos, i, j, x, y;
while(~scanf("%d %d", &m, &n)){
mark = 0;
scanf("%d", &pos);
for(i=1;i<=m;++i)
for(j=1;j<=n;++j)
scanf("%d", &A[i][j]);
for(x=1;x<=m;++x){
if(pos > A[x][n])
continue;
else break;
}
if(x>m) {print(mark); continue;}
for(y=1;y<=n;++y)
if(pos == A[x][y]){
mark = 2;
break;
}
print(mark);
}
return 0;
}
代码（二）、
题解：
1、二分查找第几行
2、二分查找第几列
#include <stdio.h>
#include <string.h>
int A[1010][1010];
void print(int flag){
if(flag == 2)
printf("Yes ");
else printf("No ");
}
int main(int argc, char const *argv[])
{
int m, n, mark, pos, i, j, x, y;
int mid, h, l;
while(~scanf("%d %d", &m, &n)){
mark = 0;
scanf("%d", &pos);
for(i=1;i<=m;++i)
for(j=1;j<=n;++j)
scanf("%d", &A[i][j]);
h = m;
l = 1;
while(l<h){
mid = (l+h)/2;
if(pos > A[mid][n])
l = mid+1;
else h = mid;
}
x = l;
if(x>m) {print(mark); continue;}
h = n+1;
l = 1;
while(l<h){
mid = (l+h)/2;
if(pos == A[x][mid]) {mark = 2; break;}
if(pos > A[x][mid])
l = mid+1;
else h = mid;
}
print(mark);
}
return 0;
}
代码（三）、
题解：
1、将二维数组转化成一维数组，进行二分查找
2、开数组注意是否爆出空间
#include <stdio.h>
int A[1000000];
int main(int argc, char const *argv[])
{
int i, pos, mul, m, n, flag;
int h, l, mid;
while(~scanf("%d %d %d", &m, &n, &pos)){
mul = m*n;
for(i=0;i<mul;++i)
scanf("%d", &A[i]);
h = mul;
flag = l = 0;
while(l<h){
mid = (h+l)/2;
if(A[mid] == pos){flag = 1; break;}
if(A[mid] > pos) h = mid;
else l = mid + 1;
}
if(flag == 1) printf("Yes ");
else printf("No ");
}
return 0;
}
代码（四）、
题解：
1、通过输入元素进行判断是否为所查找元素
#include <stdio.h>
int main()
{
int i, pos, mul, m, n, flag, dd;
while(~scanf("%d %d %d", &m, &n, &pos)){
flag = 0;
mul = m*n;
for(i=0;i<mul;++i){
scanf("%d", &dd);
if(dd == pos) flag = 1;
}
if(flag == 1) printf("Yes ");
else printf("No ");
}
return 0;
}
#include <stdio.h>
char tmp[8000];
int main()
{
int i,j,n,m,t,f,s;
while(scanf("%d%d",&n,&m)!=EOF){
scanf("%d",&t);f=0;
for(i=0;i<n;i++){
for(j=0;j<m;j++){
scanf("%d",&s);
f|=s==t;
}
if(f){
while(i<n){
fgets(tmp,8000,stdin);i++;
}
break;
}
}
if(f)printf("Yes ");
else printf("No ");
}
return 0;
}
小总结：
1、刚开始还是被输入给骗了，结果这种代码还能AC = =！
2、看来是九度OJ不想让我对自己的能力太伤心，给我放水了。
3、以上代码的思路其实是不对的。。。
4、假如题目真的像看上去那么容易，面试官也不会出这种题目吧，浪费TIME。。。
01，02，08，09
02，04，09，12
04，07，10，13
06，08，11，15
该矩阵的最小值m在左上角，最大值M在右下角。
从这样的一个矩阵中任意圈出一个子矩阵，也符合这个规律。
一个整数k，如果小于m或者大于M，则必然不在这个矩阵内。
将该矩阵分成上下两部分：
01，02，08，09
02，04，09，12
------------
04，07，10，13
06，08，11，15
如果一个整数k，大于上半部分右下角的值（这里是12），则k必然不在上半部分。
如果一个整数k，小于上半部分左上角的值（这里是04），则k必然不在下半部分。
将该矩阵分成左右两部分：
01，02 | 08，09
02，04 | 09，12
04，07 | 10，13
06，08 | 11，15
如果一个整数k，大于左半部分右下角的值（这里是08），则k必然不在左半部分。
如果一个整数k，小于右半部分左上角的值（这里是08），则k必然不在右半部分。
01：在最上面的一条边上，通过二分法查找k，找到就退出。否则，找到比k大的最小整数，将其所在及右边的列统统“切掉”。
02：在最右面的一条边上，通过二分法查找k，找到就退出。否则，找到比k小的最大整数，将其所在及上边的行统统“切掉”。
03：以上每一步中，“切”之前的矩阵大小如果为0，则失败退出；以上两步结束后，如果还没找到，则返回01，继续切。