程序员代码面试指南---001在行列都排好序的矩阵中找指定的数

题目描述

给定一个N×M的整形矩阵matrix和一个整数K, matrix的每一行和每一列都是排好序的。
实现一个函数，判断K是否在matrix中
[要求]
时间复杂度为O(N+M)，额外空间复杂度为O(1)。

输入描述

第一行有三个整数N, M, K
接下来N行，每行M个整数为输入的矩阵

输出描述

若K存在于矩阵中输出"Yes"，否则输出"No"

示例1

输入：
2 4 5
1 2 3 4
2 4 5 6
输出：
Yes

示例2

输入：
2 4 233
1 2 3 4
2 4 5 6
输出：
No

解题思路

因为是一个行列都排好序的矩阵。则从矩阵的右上角开始遍历。
如果给定的数字小于矩阵中的数字，则遍历的方向向左，
如果给定的数字大于矩阵中的数字，则遍历的方向向下。
边界条件：
遍历的行列都不能超出指定的矩阵边界。

解题代码

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

int main(){
    int N,M,K;
    cin >> N >> M >> K;
    vector< vector<int> > matrix(N,vector<int>(M));
    //构建矩阵
    for(int i = 0;i < N;i++){
        for(int j = 0;j < M;j++){
            cin>>matrix[i][j];
        }
    }
    //遍历矩阵
    //从右上角开始遍历
    int row = 0;
    int col = M - 1;
    while(row < N && col >= 0){//边界条件
        if(K == matrix[row][col]){
            cout << "Yes" << endl;
            return 0;
        }
        if(K > matrix[row][col]){
            row++;
        }else{
            col--;
        }
    }
    cout << "No" << endl;
    return 0;
}