#include <bits/stdc++.h>
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 i=0,j=M-1,res=0;
    while(i<N&&j>0){//从每一行的最后一个开始比较，因为矩阵已经排好序，
        if(Matrix[i][j]>K)
            j--;
        else if(Matrix[i][j]<K)//所以每一行最后一个比指定数小的话，这一行肯定都比其小，
            i++;//因此直接下移
        else{
            res=1;
            break;
        }
    }
    if(res==1)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}

题目描述

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

备注: 

	

		1 \leqslant N, M \leqslant 10001⩽N,M⩽1000
	


	

		0 \leqslant K, \text{矩阵中的数} \leqslant 10^90⩽K,矩阵中的数⩽109