【LeetCode 热题100】240：搜索二维矩阵 II（详细解析）（Go语言版）

🚀 力扣 240：搜索二维矩阵 II（详细解析）

📌 题目描述

力扣 240. 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。

该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

🎯 示例 1：

输入：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

🎯 示例 2：

输入：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 = 20输出：false

💡 解题思路

✅ 方法一：从右上角开始搜索（Z 字形查找）

注：该图来自于力扣题解

我们利用矩阵的有序性，从 右上角 开始：

• 若当前元素等于 target，返回 true。
• 若当前元素大于 target，说明 target 在当前列的左侧，列索引 col--。
• 若当前元素小于 target，说明 target 在当前行的下方，行索引 row++。

🔹 代码实现：

func searchMatrix(matrix [][]int, target int) bool { if len(matrix) == 0 || len(matrix[0]) == 0 { return false } rows, cols := len(matrix), len(matrix[0]) row, col := 0, cols-1 for row < rows && col >= 0 { if matrix[row][col] == target { return true } else if matrix[row][col] > target { col-- } else { row++ } } return false}

⏳ 复杂度分析：

• 时间复杂度：$O(m+n)$，最多遍历 m + n 次。
• 空间复杂度：$O(1)$，仅使用常数额外空间。

✅ 方法二：二分查找

我们可以对每一行使用 二分查找：

• 在每一行上进行 O(log n) 的搜索，总共 m 行。
• 总时间复杂度： $O(m\log n)$。

🔹 代码实现：

func binarySearch(row []int, target int) bool { left, right := 0, len(row)-1 for left <= right { mid := left + (right-left)/2 if row[mid] == target { return true } else if row[mid] < target { left = mid + 1 } else { right = mid - 1 } } return false}func searchMatrix(matrix [][]int, target int) bool { for _, row := range matrix { if binarySearch(row, target) { return true } } return false}

⏳ 复杂度分析：

• 时间复杂度：$O(m\log n)$，对每一行进行 $O(\log n)$ 的搜索。
• 空间复杂度：$O(1)$，仅使用常数额外空间。

📌 方法对比

🎯 总结

• ✅ 方法一（Z 字形查找） 是最优解，利用矩阵的有序性进行高效搜索。
• ✅ 方法二（二分查找） 在某些情况下也适用，但通常不如 O(m + n) 的解法高效。
• ✅ 该题考察 矩阵搜索技巧，类似题型包括：
  • 力扣 74. 搜索二维矩阵（每行是升序数组）
  • 力扣 378. 有序矩阵中第 K 小的元素（使用堆或二分查找）

💡 如果觉得这篇文章对你有帮助，欢迎点赞 👍、收藏 ⭐、关注 💻，持续分享更多高质量算法题解析！🎯🚀📌