程序员代码面试指南 001

在行列都排好序的矩阵中找指定的数

题目要求O(m + n)的复杂度，也就是说最多遍历一行和一列。根据矩阵有序的特点，可以根据当前元素和K值的大小关系进行查找。从右上角和左下角查找应该都可以，因为两个方向的大小关系是不同的，而左上和右下就不行了。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N, M, K;
    cin >> N >> M >> K;
    vector<vector<int>> Matrix;
    for(int i = 0; i < N; i++)
    {
        Matrix.push_back(vector<int>(M));
        for(int j = 0; j < M; j++)
        {
            cin >> Matrix[i][j];
        }
    }
    bool bFind = false;
    size_t i = 0, j = M;
    while(i < N && j > 0){
        if(K < Matrix[i][j - 1]) j--;
        else if(K > Matrix[i][j - 1]) i++;
        else{
            bFind = true;
            break;
        }
    }
    if(bFind) cout << "Yes" << endl;
    else cout << "No" << endl;
}