本文共 1372 字，大约阅读时间需要 4 分钟。

剑指Offer04-二维数组中查找

问题描述

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

解题思路

这种方法充分利用了矩阵的有序性质，能够在较少的查找次数内找到目标值，时间复杂度为O(log n + log m)。

解决代码

public class Solution {    public boolean findNumberIn2DArray(int[][] matrix, int target) {        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {            return false;        }        int rows = matrix.length;        int cols = matrix[0].length;        int row = 0;        int col = cols - 1;        while (row < rows && col >= 0) {            int num = matrix[row][col];            if (num == target) {                return true;            } else if (target > num) {                row++;            } else {                col--;            }        }        return false;    }}

代码解释

• 初始检查： 检查矩阵是否为空，避免后续操作。
• 确定行和列的范围： 从右上角开始查找。
• 循环查找： 在每次循环中，比较当前位置的值与目标值，决定下一步的行或列索引。
• 终止条件： 当行索引超过矩阵行数或列索引小于0时，说明目标值不存在，返回false。

这种方法高效且简洁，能够在较短时间内完成查找任务，适用于大规模的二维数组。

转载地址：http://yydmz.baihongyu.com/