当前位置：首页 > article >正文

搜索二维矩阵——巧用右上角起点搜索法，高效解决二维矩阵查找问题

article 2025/2/11 16:39:58

📖 问题描述

给定一个满足以下特性的 m x n 整数矩阵：

每行元素从左到右非严格递增
每行的第一个元素大于前一行的最后一个元素

要求判断目标值 target 是否存在于矩阵中。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

🔍 算法解析

特性分析

该矩阵具有以下重要性质：

行内有序：每行元素从左到右保持非递减
行间严格递增：下一行的最小值 > 当前行的最大值

这意味着我们可以将这个二维矩阵展开视为一个严格递增的一维数组，直接使用二分搜索。但本文将介绍一种更直观的双指针法。

右上角起点搜索法

我们从矩阵的右上角（或左下角）开始搜索，利用矩阵特性缩小查找范围：

起点选择：初始位置设为右上角元素 matrix[0][n-1]
比较逻辑：
- 若当前值 = target → 找到目标，返回true
- 若当前值 < target → 排除当前行（向下移动）
- 若当前值 > target → 排除当前列（向左移动）

这种策略每次操作都能排除一行或一列，将时间复杂度控制在 O(m+n)。

🖥 代码实现

class Solution {
    public boolean searchMatrix(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 current = matrix[row][col];
            if (current == target) {
                return true; // 找到目标值
            } else if (current < target) {
                row++; // 排除当前行，向下搜索
            } else {
                col--; // 排除当前列，向左搜索
            }
        }
        return false; // 搜索完毕未找到
    }
}