二、剑指offer：04. 二维数组中的查找

04. 二维数组中的查找

一、题目描述

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例：
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000

二、解题思路

1、线性查找法

思路：

由提示例可以观测到，二维数组的行从左至右依次增大，从上之下依次增大；
那么就可以利用这个规律进行查找；有两种思路：

1、从第一行最后一列matrix[0] [j]开始与目标值target比较
①、如果二维数组为空，则返回false；
②、如果当前值大于目标值target，则列-1；
③、如果当前值小于目标值target，则行+1;
④、当前值等于目标值target，则返回true；

伪代码：

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        //首先判断二维数组是否为空
        if(matrix.size() == 0)
            return false;
        
        int row = 0;	//定义行
        int col = matrix[0].size() - 1;	//定义列
       
        while(row < matrix.size() && col >= 0)	//循环
        {
            if(matrix[row][col] > target)	//从矩阵 matrix右上角元素开始遍历与target比较
                col--;	//大于target则列递减
            else if(matrix[row][col] < target)
                row++;	//小于target则行递减
            else if(matrix[row][col] == target)
                return true;	//等于target则返回true
        }
        return false;
    }
};

2、从最后一行第一列matrix[i] [0]开始与目标值 (target) 比较
①、如果二维数组为空，则返回false；
②、如果当前值大于目标值target，则行-1；
③、如果当前值小于目标值target，则列+1;
④、当前值等于目标值target，则返回true；

伪代码：

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
     	//首先判断二维数组是否为空
   		if(matrix.size() == 0)
            return false;
        
        int i = matrix.size() - 1;	//定义左下角最后一行
        int j = 0;	//定义右上角第一列
        while(i >= 0 && j < matrix[0].size())
        {
            if(matrix[i][j] > target) i--;	//小于target，行上移
            else if(matrix[i][j] < target) j++;	//大于target，列下移
            else return true;
        }
        return false;
    }
};

复杂度分析：

时间复杂度：O(n+m)。访问到的下标的行最多增加 n 次，列最多减少 m 次，因此循环体最多执行 n + m 次。
空间复杂度：O(1)。

2、具体程序实现：

#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
	bool findNumberIn2DArray(vector<vector<int> > v, int target)
	{
		//1、判断二维数组是否为空
		if(v.size() == 0)
		{
			return false;
		}
		
		int i = 0;//二维数组行
		int j = v[0].size() - 1;//二维数组列
		
		while(i < v.size() && j >= 0)
		{
			//2、如果当前数值大于target，则列-1
			if(v[i][j] > target)
			{
				j--;
			}
			else if(v[i][j] < target) //3、如果当前值小于target则行+1
			{
				i++;
			}
			else if(v[i][j] == target)
			{
				return true;
			}
		}
		return false;		
	}
};


int main()
{
	vector<vector<int> > v1(5,vector<int>(5));
	int arry[5][5] = {
		{1, 4, 7, 11, 15},
		{2, 5, 8, 12, 19},
		{3, 6, 9, 16, 22},
		{10, 13, 14, 17, 24},
		{18, 21, 23, 26, 30}};
	
	for(int i = 0; i < 5; i++ )
	{
		for(int j = 0; j < 5; j++)
		{
			v1[i][j] = arry[i][j];
		}
	}
	
	Solution s;
	if(s.findNumberIn2DArray(v1,12))
	{
		cout << "找到了" << endl;
	}
	else
	{
		cout << "没有找到" << endl;
	}
	
   return 0;
}