题解 | #二维数组中的查找#

题目的主要信息：

• 矩阵的行元素和列元素都是有序的，从左到右递增，从上到下递增，完全递增元素不会有重复
• 找到矩阵中有没有给定元素即可

举一反三：

学习完本题的思路你可以解决如下题目：

BM17.二分查找-I

BM19.寻找峰值

BM21.旋转数组

方法：二分查找（推荐使用）

知识点：分治

分治即“分而治之”，“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题，子问题继续按照这样划分，直到问题可以被轻易解决；“治”指的是将子问题单独进行处理。经过分治后的子问题，需要将解进行合并才能得到原问题的解，因此整个分治过程经常用递归来实现。

思路：

似乎我们可以直接从上到下遍历矩阵，再从左到右遍历矩阵每一行，然后检验目标值是否是遇到的元素。

//两层循环，遍历二维数组
for(int i = 0; i < n; i++)  
    for(int j = 0; j < m; j++)
        //找到target
        if(array[i][j] == target)  
            return true;

但是我们这样就没有利用到矩阵内部的行列都是有序这个性质，我们再来找找规律：

首先看四个角，左上与右下必定为最小值与最大值，而左下与右上就有规律了：左下元素大于它上方的元素，小于它右方的元素，右上元素与之相反。既然左下角元素有这么一种规律，相当于将要查找的部分分成了一个大区间和小区间，每次与左下角元素比较，我们就知道目标值应该在哪部分中，于是可以利用分治思维来做。

具体做法：

• step 1：首先获取矩阵的两个边长，判断特殊情况。
• step 2：首先以左下角为起点，若是它小于目标元素，则往右移动去找大的，若是他大于目标元素，则往上移动去找小的。
• step 3：若是移动到了矩阵边界也没找到，说明矩阵中不存在目标值。

图示：

Java实现代码：

public class Solution {
    public boolean Find(int target, int [][] array) {
        //优先判断特殊
        if(array.length == 0)  
            return false;
        int n = array.length;
        if(array[0].length == 0)  
            return false;
        int m = array[0].length;
        //从最左下角的元素开始往左或往上
        for(int i = n - 1, j = 0; i >= 0 && j < m; ){ 
            //元素较大，往上走
            if(array[i][j] > target)   
                i--;
            //元素较小，往右走
            else if(array[i][j] < target) 
                j++;
            else
                return true;
        }
        return false;
    }
}

C++实现代码：

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        //优先判断特殊
        if(array.size() == 0)  
            return false;
        int n = array.size();
        if(array[0].size() == 0)  
            return false;
        int m = array[0].size();
        //从最左下角的元素开始往左或往上
        for(int i = n - 1, j = 0; i >= 0 && j < m; ){ 
            //元素较大，往上走
            if(array[i][j] > target)   
                i--;
            //元素较小，往右走
            else if(array[i][j] < target) 
                j++;
            else
                return true;
        }
        return false;
    }
};

Python实现代码：

class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # 优先判断特殊
        if len(array) == 0: 
            return False
        n = len(array)
        if len(array[0]) == 0:
            return False
        m = len(array[0])
        i = n-1
        j = 0
        # 从最左下角的元素开始往左或往上
        while i >=0 and j < m: 
            # 元素较大，往上走
            if array[i][j] > target: 
                i -= 1
            # 元素较小，往右走
            elif array[i][j] < target: 
                j += 1
            else:
                return True
        return False

复杂度分析：

• 时间复杂度：$O(m+n)O(m+n)$，遍历矩阵的时候，最多经过矩阵的一行一列
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外辅助空间