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;}
}

解题思路

二维矩阵当作一维数组：

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

二分查找：

使用二分查找法，初始化 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 为例：

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

以 target = 13 为例：

初始化：m = 3, n = 4，left = 0, right = 11
第一次迭代：
计算 mid = 5 ((0 + 11) / 2)
midValue = matrix[5 / 4][5 % 4] = matrix[1][1] = 11
midValue < target，移动左指针：left = 6

第二次迭代：
计算 mid = 8 ((6 + 11) / 2)
midValue = matrix[8 / 4][8 % 4] = matrix[2][0] = 23
midValue > target，移动右指针：right = 7

第三次迭代：
计算 mid = 6 ((6 + 7) / 2)
midValue = matrix[6 / 4][6 % 4] = matrix[1][2] = 16
midValue > target，移动右指针：right = 5

退出循环，返回 false。