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[][];

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 ;

}

巴特西

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

最新文章

热门文章