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

【LeetCode 热题100】74：搜索二维矩阵（二分、线性两种方式详细解析）（Go 语言实现）

article 2025/2/11 6:25:59

🚀 力扣热题 74：搜索二维矩阵（详细解析）

📌 题目描述

力扣 74. 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵 matrix ：

每行中的整数从左到右按非递减顺序排列。
每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false。

🎯 示例 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
✅ 提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4

💡 解题思路

1. 观察矩阵特性

矩阵每行递增，且下一行的第一个元素大于上一行的最后一个元素。
可以将其视为一个 一维有序数组，索引从 0 到 m * n - 1，然后用 二分查找 解决。

2. 方法一：二分查找

视整个二维数组为一维数组，使用索引 mid，计算对应的二维坐标：
```
row = mid // n  (行号)
col = mid % n  (列号)
```
进行标准的 二分查找：
- 如果 matrix[row][col] == target，返回 true。
- 如果 matrix[row][col] < target，移动左边界。
- 如果 matrix[row][col] > target，移动右边界。

💻 Go 代码实现（方法一：二分查找）

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }
    
    m, n := len(matrix), len(matrix[0])
    left, right := 0, m*n-1
    
    for left <= right {
        mid := (left + right) / 2
        row, col := mid/n, mid%n
        
        if matrix[row][col] == target {
            return true
        } else if matrix[row][col] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return false
}

3. 方法二：逐行扫描 + 线性查找

遍历每一行，判断 target 是否在当前行范围内（即 row[0] <= target <= row[n-1]）。
如果在范围内，则进行遍历查找。
适用于矩阵较小的情况，时间复杂度较高。

💻 Go 代码实现（方法二：逐行扫描）

func searchMatrix(matrix [][]int, target int) bool {
    for i := range matrix {
        num := matrix[i]
        if num[0] <= target && target <= num[len(num)-1] {
            for j := range num {
                if num[j] == target {
                    return true
                }
            }
        }
    }
    return false
}