LeetCode 剑指 Offer 04. 二维数组中的查找

Categories:

Tags:

题目描述
思路分析
1. 解法一：右上角 Z 字形搜索（推荐）
相似题目

题目描述

✅ 剑指 Offer 04. 二维数组中的查找

思路分析

解法一：右上角 Z 字形搜索（推荐）

核心思路：

从矩阵右上角出发，该位置是当前行最大值、当前列最小值。

若当前值大于目标值，向左移动排除一整列；若小于目标值，向下移动排除一整行。

每次移动都能排除一行或一列，直到越界或找到目标。

复杂度分析：

时间复杂度：O(m + n)，其中 m、n 分别为行数与列数。

空间复杂度：O(1)，只使用常数额外空间。

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int row = 0;
        int col = matrix[0].length - 1;

        // 从右上角出发，逐步排除行或列
        while (row < matrix.length && col >= 0) {
            int val = matrix[row][col];
            if (val == target) {
                return true;
            }
            if (val > target) {
                col--;
            } else {
                row++;
            }
        }

        return false;
    }
}

func findNumberIn2DArray(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }

    row, col := 0, len(matrix[0])-1

    // 从右上角出发，逐步排除行或列
    for row < len(matrix) && col >= 0 {
        val := matrix[row][col]
        if val == target {
            return true
        }
        if val > target {
            col--
        } else {
            row++
        }
    }

    return false
}

相似题目

题目	难度	考察点
74. 搜索二维矩阵	中等	二分查找
240. 搜索二维矩阵 II	中等	矩阵搜索
33. 搜索旋转排序数组	中等	二分查找
704. 二分查找	简单	二分查找
378. 有序矩阵中第 K 小的元素	中等	二分/堆

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/26553981