Cracking the coding interview--Q9.6

January 21, 2013
作者:Hawstein
出处:http://hawstein.com/posts/9.6.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

Given a matrix in which each row and each column is sorted, write a method to find an element in it.

译文:

给出一个矩阵,其中每一行和每一列都是有序的,写一个函数在矩阵中找出指定的数。

解答

我们假设这个矩阵每一行都是递增的,每一列也都是递增的,并把这些数据存入文件 9.6.in(如下),其中开头的两个数5 5表示该矩阵是5*5的。

5 5
1 2 3 4 5
3 7 8 9 11
5 9 10 17 18
7 12 15 19 23
9 13 16 20 25

这个矩阵是有序的,因此我们要利用这一点,当矩阵中元素和要查找的元素对比后, 如果相等,我们返回下标;如果不等,我们就排除掉一些元素,而不仅仅是对比的元素。 我们从矩阵的四个角的元素入手看看,有什么特点。左上角是最小的, 因为矩阵向右是递增的,向下也是递增的。同理,右下角是最大的。让我们来看看右上角, 设要查找的元素为x,比如x比右上角元素5大,那么它也会比第一行的其它元素都大。 因此可以去掉第一行;如果它比右上角元素小,那么它也会比最后一列的元素都小, 因此可以去掉最后一列;然后这样不断地比下去,只需要O(m+n)的时间就查找完。 对于左下角的元素,也有一样的特点。就不再分析了。

代码如下:

#include <iostream>
#include <cstdio>
using namespace std;

int d[20][20];
int search(int m, int n, int x){
    int r = 0, c = n-1;
    while(r<m && c>=0){
        if(d[r][c] == x) return (r * n + c);
        else if(d[r][c] < x) ++r;
        else --c;
    }
    return -1;
}
int main(){
    freopen("9.6.in", "r", stdin);
    int m, n;
    cin>>m>>n;
    for(int i=0; i<m; ++i)
        for(int j=0; j<n; ++j)
            cin>>d[i][j];

    int k = search(m, n, 13);
    if(k == -1) cout<<"not found"<<endl;
    else cout<<"position: "<<k/n<<" "<<k%n<<endl;
    fclose(stdin);
    return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview