剑指offer-二维数组中的查找

本文属于剑指offer系列第一题。
本题目的关键点在于找到一个非常棒的问题入手点，然后这个题目就已经解决了一半。

题目描述

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

解题思路

思路1: 双层for循环，肯定能解决，但是复杂度为O(n^2),而且没有充分利用行列有序这个条件。
思路2: 我们从右上角开始查找，往左下角找。
如果当前位置的元素大于目标元素，那么肯定在下一行。
如果当前位置的元素小于目标元素，肯定在本元素的左侧。
如果当前位置的元素等于目标元素，那么返回即可。

巧妙之处

题目从右上角入手开始查找元素非常有效且巧妙。

解题代码

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
       int i = 0;
       int j = array[0].size()-1;
       while(i < array.size() && j>= 0){
           if(array[i][j] == target){
               return true;
           }else if(array[i][j] < target){
               i++;
           }else{
               j--;
           }
       }
       return false;
    }
};

时间复杂度是O(m+n)，空间复杂度O(m*n) m为行数，n为列数。
以上，本题结束！