题目链接:http://219.244.176.199/JudgeOnline/problem.php?id=1214
这是这次微软实习面试的一道题,题目大意就是:有一个n*m的矩阵,已知它每一行都是不严格递增的,而且每一行的任意数都比前一行的任意数大或等于。给你一个数k,请你判断k是否存在于矩阵中。
当时想到的方法是二分第一列,就能确定k位于哪一行,然后二分这一行,得到是否存在k。二分第一列的复杂度是O(logn),二分那一行的复杂度是O(logm),所以总的复杂度是O(logn+logm)。
不过上面的写法需要写两个二分。其实二维数组在内存中是连续的一段内存,所以我们可以直接把二维数组看成一个一维数组b,那么b[p]对应的就是a[p/m][p%m]。这样的话就可以直接进行一维数组的二分了。复杂度是O(logmn)。
其实两个的时间复杂度是一致的,只是写法第二种稍微简单一点。
代码:二分+二分
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#define LL long long using namespace std; int a[][];
int n, m, q; void input()
{
for (int i = ; i < n; ++i)
for (int j = ; j < m; ++j)
scanf("%d", &a[i][j]);
} bool binSearch(int k)
{
int lt = , rt = n-, mid, row;
while (lt+ < rt)
{
mid = (lt+rt)>>;
if (a[mid][] <= k) lt = mid;
else rt = mid;
}
if (a[rt][] <= k) row = rt;
else row = lt; lt = ; rt = m-;
while (lt+ < rt)
{
mid = (lt+rt)>>;
if (a[row][mid] <= k) lt = mid;
else rt = mid;
}
if (a[row][lt] == k) return true;
if (a[row][rt] == k) return true;
return false;
} void work()
{
int k;
scanf("%d", &q);
for (int i = ; i < q; ++i)
{
scanf("%d", &k);
if (binSearch(k)) printf("Yes\n");
else printf("No\n");
}
} int main()
{
//freopen("test2.in", "r", stdin);
//freopen("test3.out", "w", stdout);
while (scanf("%d%d", &n, &m) != EOF)
{
input();
work();
} return ;
}
代码:看成一维二分
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#define LL long long using namespace std; int a[][];
int n, m, q; void input()
{
for (int i = ; i < n; ++i)
for (int j = ; j < m; ++j)
scanf("%d", &a[i][j]);
} bool binSearch(int k)
{
int lt = , rt = n*m-, mid;
while (lt+ < rt)
{
mid = (lt+rt)>>;
if (a[mid/m][mid%m] <= k) lt = mid;
else rt = mid;
}
if (a[lt/m][lt%m] == k) return true;
if (a[rt/m][rt%m] == k) return true;
return false;
} void work()
{
int k;
scanf("%d", &q);
for (int i = ; i < q; ++i)
{
scanf("%d", &k);
if (binSearch(k)) printf("Yes\n");
else printf("No\n");
}
} int main()
{
//freopen("test2.in", "r", stdin);
//freopen("test3.out", "w", stdout);
while (scanf("%d%d", &n, &m) != EOF)
{
input();
work();
} return ;
}