面试题3
题目描述：
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
输入：
输入可能包含多个测试样例，对于每个测试案例，
输入的第一行为两个整数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
空间复杂度都是O（n*m)
第一种思路：直接遍历一遍，时间复杂度O（n*m）；
提交后耗时900ms
#include<iostream>
#include<cstring>
#include<cstdio>
using std::cin;
using std::endl;
using std::cout;
const int MAX = 1000005;
int num[ MAX ];
int main(){
int n, m, t, temp;
while( scanf( "%d %d", &n, &m ) != EOF ){
scanf( "%d", &temp );
memset( num, 0, sizeof( num ) );
for( int i = 0; i < n; ++i ){
for( int j = 0; j < m; ++j ){
//cin >> t;
scanf( "%d", &t );
num[ t ]++;
}
}
if( num[ temp ] )
puts( "Yes" );
else
puts( "No" );
}
return 0;
}
第二种思路：采用二分查找，适用于数据无规律情况。
时间复杂度为O（NlogN， N= n*m),
提交耗时670ms
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<algorithm>
#include<functional>
#include<stack>
using namespace std;
const int MAX = 1005;
int num[MAX * MAX ];
bool FindTheNumber(int *num, int Rows, int Columns, int number){
int l = 0;
int r = Rows * Columns;
bool found = false;
if (num != NULL && Rows >= 0 && Columns >= 0){
while (l <= r ){
int mid = (l + r) / 2;
if (num[l] == number ?? num[r] == number ?? num[mid] == number){
found = true;
break;
}
else if (number < num[mid])
r = mid - 1;
else
l = mid + 1;
}
}
return found;
}
int main(){
int n, m, number;
//while ( cin >> n >> m ){
while (scanf( "%d%d", &n, &m ) != EOF ){
//cin >> number;
scanf("%d", &number);
for (int i = 0; i < n; ++i){
for (int j = 0; j < m; ++j){
//cin >> num[ i * n + j];
scanf("%d", &num[ i *m + j ] );
}
}
bool flag = FindTheNumber(num, n, m, number);
if (flag)
puts("Yes");
else
puts("No");
}
}
第三种思路：适用于本题所给的条件。根据题意。在一个二维数组中，数据自左向右增大，自上而下增大。由此第一反应就是左上角数据最小，右下角数据最大。这样的话一开始很容易联想到，是不是可以从对角线出发，自左上角向右下角去查找。或许可行，没有尝试，因为感觉处理起来会比较麻烦。（未尝试）
但是下面这样处理就简单很多了。我们分别从左上角和右上角分别自上而下、自右向左查找。假设右上角的值大于当前查找值，则我们可以略过对最后一列的查找（自上而下增大，目前最小值大于查找值）。由此我们一直向左找到第一行小于查找值，这时所查找值可能位于当前列。同理，查询行，假设已经找到可能存在的列的第一行的值小于查找值，那么其左边的值都可以略过（自左向右增大，该行最大值小于查找值）。这样可以略过该行。直到查到查找值或者遍历完毕。未尝试的那种思路也可以这样理解，只不过那样处理起来是矩形的范围。
时间复杂度为O（n+m）。这种思路的提交耗时为700ms
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<algorithm>
#include<functional>
#include<stack>
using namespace std;
const int MAX = 1005;
int num[MAX * MAX ];
bool FindTheNumber(int *num, int Rows, int Columns, int number){
bool found = false;
if (num != NULL && Rows > 0 && Columns > 0){
int row = 0;
int column = Columns - 1;
while (row < Rows && column >= 0){
if (num[row * Columns + column] == number){
found = true;
break;
}
else if (num[row * Columns + column] > number){
column--;
}
else
row++;
}
}
return found;
}
int main(){
int n, m, number;
while (scanf( "%d%d", &n, &m ) != EOF ){
//cin >> number;
scanf("%d", &number);
for (int i = 0; i < n; ++i){
for (int j = 0; j < m; ++j){
//cin >> num[ i * n + j];
scanf("%d", &num[i * m + j]);
}
}
bool flag = FindTheNumber(num, n, m, number);
if (flag)
puts("Yes");
else
puts("No");
}
}