leetcode hot100【LeetCode 74.搜索二维矩阵】java实现

LeetCode 74.搜索二维矩阵

题目描述

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

每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ，如果 target
在矩阵中，返回 true ；否则，返回 false 。

示例 1:

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

示例 2:

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

Java 实现代码

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length;int n = matrix[0].length;int left = 0, right = m * n - 1;while (left <= right) {int mid = left + (right - left) / 2;int midValue = matrix[mid / n][mid % n];if (midValue == target) {return true;} else if (midValue < target) {left = mid + 1;} else {right = mid - 1;}}return false;}
}

解题思路

1. 二维矩阵当作一维数组：

   • 将二维矩阵看作一个长度为 m * n 的一维数组。
   • 矩阵中索引 (row, col) 可以通过一维索引 mid 计算得到：
     • 行号：row = mid / n
     • 列号：col = mid % n

2. 二分查找：

   • 使用二分查找法，初始化 left = 0，right = m * n - 1。
   • 计算中间索引 mid，根据其映射的矩阵元素 matrix[mid / n][mid % n] 进行比较。
   • 如果 matrix[mid / n][mid % n] == target，返回 true。
   • 如果小于 target，则移动左指针。
   • 如果大于 target，则移动右指针。

复杂度分析

• 时间复杂度：O(log(m * n)) 二分查找在 m * n 个元素中查找目标值，因此时间复杂度为 O(log(m * n))。
• 空间复杂度：O(1)。我们只使用了常量级别的额外空间来存储索引。

执行过程示例

以 matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]，target = 11 为例：

1. 初始化：m = 3, n = 4，left = 0, right = 11
2. 第一次迭代：
   • 计算 mid = 5 ((0 + 11) / 2)
   • midValue = matrix[5 / 4][5 % 4] = matrix[1][1] = 11
   • midValue == target，返回 true。

以 target = 13 为例：

1. 初始化：m = 3, n = 4，left = 0, right = 11
2. 第一次迭代：
   • 计算 mid = 5 ((0 + 11) / 2)
   • midValue = matrix[5 / 4][5 % 4] = matrix[1][1] = 11
   • midValue < target，移动左指针：left = 6
3. 第二次迭代：
   • 计算 mid = 8 ((6 + 11) / 2)
   • midValue = matrix[8 / 4][8 % 4] = matrix[2][0] = 23
   • midValue > target，移动右指针：right = 7
4. 第三次迭代：
   • 计算 mid = 6 ((6 + 7) / 2)
   • midValue = matrix[6 / 4][6 % 4] = matrix[1][2] = 16
   • midValue > target，移动右指针：right = 5
5. 退出循环，返回 false。