ACM学习历程—SNNUOJ1214 矩阵1(二分)

题目链接：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[1005][1005];
int n, m, q;

void input()
{
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            scanf("%d", &a[i][j]);
}

bool binSearch(int k)
{
    int lt = 0, rt = n-1, mid, row;
    while (lt+1 < rt)
    {
        mid = (lt+rt)>>1;
        if (a[mid][0] <= k) lt = mid;
        else rt = mid;
    }
    if (a[rt][0] <= k) row = rt;
    else row = lt;

    lt = 0; rt = m-1;
    while (lt+1 < rt)
    {
        mid = (lt+rt)>>1;
        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 = 0; i < q; ++i)
    {
        scanf("%d", &k);
        if (binSearch(k)) printf("Yes
");
        else printf("No
");
    }
}

int main()
{
    //freopen("test2.in", "r", stdin);
    //freopen("test3.out", "w", stdout);
    while (scanf("%d%d", &n, &m) != EOF)
    {
        input();
        work();
    }

    return 0;
}

 

 

代码：看成一维二分

#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[1005][1005];
int n, m, q;

void input()
{
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            scanf("%d", &a[i][j]);
}

bool binSearch(int k)
{
    int lt = 0, rt = n*m-1, mid;
    while (lt+1 < rt)
    {
        mid = (lt+rt)>>1;
        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 = 0; i < q; ++i)
    {
        scanf("%d", &k);
        if (binSearch(k)) printf("Yes
");
        else printf("No
");
    }
}

int main()
{
    //freopen("test2.in", "r", stdin);
    //freopen("test3.out", "w", stdout);
    while (scanf("%d%d", &n, &m) != EOF)
    {
        input();
        work();
    }

    return 0;
}