剑指 offer 面试题精选图解 04 . 二维数组中的查找

作者：程序员吴师兄

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 04 . 二维数组中的查找。

题目链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

一、题目描述

在一个 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

二、题目解析

仔细观察矩阵，可以发现：左下角元素 为所在列最大元素，所在行最小元素

如果 左下角元素 大于了目标值，则目标值一定在该行的上方， 左下角元素所在行可以消去。

如果 左下角元素 小于了目标值，则目标值一定在该列的右方， 左下角元素所在列可以消去。

具体操作为从矩阵左下角元素开始遍历，并与目标值对比：

• 当 matrix[i][j] > target 时：行索引向上移动一格（即 i--），即消去矩阵第 i 行元素；
• 当 matrix[i][j] < target 时：列索引向右移动一格（即 j++），即消去矩阵第 j 列元素；
• 当 matrix[i][j] == target 时：返回 true。
• 如果越界，则返回 false。

三、动画描述

四、图片描述

面试题04. 二维数组中的查找.001

面试题04. 二维数组中的查找.002

面试题04. 二维数组中的查找.003

面试题04. 二维数组中的查找.004

面试题04. 二维数组中的查找.005

面试题04. 二维数组中的查找.006

面试题04. 二维数组中的查找.007

面试题04. 二维数组中的查找.008

面试题04. 二维数组中的查找.009

面试题04. 二维数组中的查找.010

面试题04. 二维数组中的查找.011

面试题04. 二维数组中的查找.012

面试题04. 二维数组中的查找.013

面试题04. 二维数组中的查找.014

面试题04. 二维数组中的查找.015

面试题04. 二维数组中的查找.016

面试题04. 二维数组中的查找.017

面试题04. 二维数组中的查找.018

面试题04. 二维数组中的查找.019

五、参考代码

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        //初始化 i 和 j 为数组左下角元素
        int i = matrix.length - 1, 
        int j = 0;
        //如果 i 和 j 没有越界继续判断
        while(i >= 0 && j < matrix[0].length){
            
            if(matrix[i][j] > target){
                //行索引向上移动一格（即 i-- ），即消去矩阵第 i 行元素
                i--;
            }else if(matrix[i][j] < target){
                //列索引向右移动一格（即 j++ ），即消去矩阵第 j 列元素
                j++;
            }else{
                //找到目标值，直接返回 ture
                return true;
            }     
        }
        //没有找到目标值，返回 false
        return false;
    }
}

六、复杂度分析

时间复杂度

时间复杂度为 O(M+N)，其中，N 和 M 分别为矩阵行数和列数，此算法最多循环 M + N 次。

空间复杂度

空间复杂度为 O(1)。

七、相关标签

• 数组
• 双指针
• 二分法