题解

题目难度：简单
知识点：数学逻辑、数组

方法一：

思路：
1：将数据输入动态数组matrix中，从左下脚开始遍历，初始行数i=m-1,初始列数j=0。

2：判断现在所在行数i，j=0，即matrix[i][0]与K值进行比较，如果matrix[i][0]>k,由于每行元素值依次增大，所以一定不在该行，i--之后重复第2步。

3.如果matrix[i][0]<k,遍历该行的所有列j，如果存在matrix[i][j]=k,打印true，使用return语句结束程序；当出现matrix[i][j]>k时，表明该行j+1到n列都不会出现matrix[i][j]=k的情况，因此将i--，重复第2步。如果当j=n时未出现上两种情况，需要继续判断上一行，也跳转到第2步。

4.遍历完所有的i时，没有遇到return结束程序语句，即没有出现matrix[i][j]=k，打印false。

时间复杂度O(m+n)，空间复杂度O(m*n)

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int m, n, k;
    cin >> m >> n;
    vector< vector<int> > matrix;
    for(int i = 0; i < m; i++) {
        vector<int> temp;
        for(int j = 0; j < n; j++) {
            cin >> k;
            temp.push_back(k);
        }
        matrix.push_back(temp);
    }
    cin >> k;
    for(int i=m-1;i>=0;i--){
        if(matrix[i][0]>k) continue;
        else{
            for(int j=0;j<n;j++){
                if(matrix[i][j]==k){
                    cout<<"true"<<endl;
                    return 0;
                }
                if(matrix[i][j]>k){
                    break;
                }
            }
        }
    }
    cout<<"false"<<endl;
    return 0;
}

方法二：以空间换时间

从题干可知：矩阵中出现的数字与需要查找的数(k)都为0~100000之间的整数。因此我们用一个布尔型数组M，将其大小设置为1000001，矩阵中出现的每一个数字num,将M[num]值设置为true。最后判断需要查找的数k，即m[k]是否为true。如果为true输出true，否者输出false。

时间复杂度O(1)，空间复杂度O(N)

#include <iostream>
using namespace std;
int main(){
    int m,n,num;
    bool M[100001];
    cin>>m>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            cin>>num;
            M[num] = true;
        }
    int k;
    cin>>k;
    if(!M[k])
        cout<<"false"<<endl;
    else
        cout<<"true"<<endl;
    return 0;
}