CentOS 7.0 环境编译thinstation

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.empty()){
            return false;
        }     
        int i = 0;
        int j1 = array.size() - 1;
        int j2 = array[0].size() - 1;

        int min = array[0][0];
        int max = array[j1][j2];

        if ( target < min || target > max){
            return false;
        }

        while ( i < j1 && j2 >= 0){
            if( target < array[i][j2] ){
                j--;
            }else if( target > array[i][j2] ){
                i++;
            }else{
                return true;
            }
        }
        return false;   
    }
};

解析

信息：

1. 最小数（min）是第一行第一个，最大数（max）是最后一行的最后一个
2. 每一行最大的一个数是每一行的最后一个，每一行最小一个数是每一行的第一个

Key Mind:

先从第一行的最后一个数（称为J），开始比较，如果目标大于J，则与下一行的最后一个数比较，如此循环，直到目标比J小，当目标比J小时，我们就能确定是哪一行

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 876208453@qq.com