题意概述

• 给定一个每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序二维数组和一个整数
• 问整数是否在二维数组中，存在返回true，否则返回false

方法一：暴力

思路与具体做法

• 容易知道遍历整个二维数组，如果查找到了该值，则说明该值存在返回true，否则返回false

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        for(int i=0;i<array.size();i++){//遍历行
        	for(int j=0;j<array[i].size();j++){//遍历列
				if(array[i][j]==target)return true;//如果找到元素则返回
			} 
		}
		return false;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(nm\right)O(nm)$O(nm)，遍历了整个二维数组
• 空间复杂度：$O\left(1\right)O(1)$O(1)，仅用到了常数个变量

方法二：线性查找

思路与具体做法

• 根据给定二维数组按行从左到右递增，按列从上到下递增的特点
• 即对数组中每个元素，左边比其小，右边都比其大，上面都比其小，下面都比其大
• 选定二维数组右上角开始查找
  • 如果当前元素等于target，则返回true
  • 如果当前元素大于target，则向左移动
  • 如果当前元素小于target，则向下移动
  • 最后总可以找到目标值

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
    	int x=0,y=array[0].size()-1;//从二维数组右上角开始
        while(x<array.size()&&y>=0){//没有超过边界
        	int t=array[x][y];
        	if(t==target){//当前元素等于target，则返回true
        		return true;
			}else if(t>target)y--;//如果当前元素大于target，则向左移动
			else x++;//如果当前元素小于target，则向下移动
		}
		return false;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O(n+m)O(n+m)$O(n+m)，最坏情况下从二维数组右上角查找到二维数组左下角，下移n行，左移m列
• 空间复杂度：$O\left(1\right)O(1)$O(1)， 仅用到了常数个变量