LeetCode[中等] 74.搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
public class Solution {public bool SearchMatrix(int[][] matrix, int target) {int m = matrix.Length, n = matrix[0].Length;int low = 0, high = m * n - 1;while(low <= high){int mid = low + (high - low) / 2;int row = mid / n , column = mid % n;if(matrix[row][column] == target)return true;else if(matrix[row][column] > target)high = mid -1;elselow = mid + 1;}return false;}
}思路：m 行 n 列的矩阵可以转换成长度为 mn 的升序数组。矩阵中的每个位置可以和升序数组中的下标转换：
-
当 0≤i<m 且 0≤j<n 时，矩阵的第 i 行第 j 列等价于升序数组的下标 i×n+j；
-
当 0≤index<mn 时，升序数组的下标 index 等价于矩阵的第 ⌊nindex⌋ 行第 index mod n 列。
为了判断矩阵中是否存在目标值，可以在矩阵转换成的升序数组中二分查找。
复杂度分析
代码
测试用例
测试结果
测试结果
全部题解
74. 搜索二维矩阵
Storm
关注
242
2022.06.11
发布于 上海
数组
二分查找
矩阵
C
6+
解法
思路和算法
由于给定的矩阵满足每行升序排序，且每行的第一个整数大于前一行的最后一个整数，因此如果将矩阵的每一行拼接到前一行的末尾，可以得到一个升序数组，m 行 n 列的矩阵可以转换成长度为 mn 的升序数组。矩阵中的每个位置可以和升序数组中的下标转换：
-
当 0≤i<m 且 0≤j<n 时，矩阵的第 i 行第 j 列等价于升序数组的下标 i×n+j；
-
当 0≤index<mn 时，升序数组的下标 index 等价于矩阵的第 ⌊nindex⌋ 行第 indexmodn 列。
为了判断矩阵中是否存在目标值，可以在矩阵转换成的升序数组中二分查找。
用 low 和 high 分别表示二分查找的下标范围的下界和上界，初始时 low=0，high=mn−1。每次查找时，取 mid 为 low 和 high 的平均数向下取整，计算下标 mid 对应的矩阵行下标和列下标，判断矩阵中的相应位置的数和目标值的大小关系，调整查找的下标范围。
-
如果矩阵中相应位置的数等于 target，则找到目标值，返回 true。
-
如果矩阵中相应位置的数大于 target，则如果目标值存在，其下标一定小于 mid，因此在下标范围 [low,mid−1] 中继续查找。
-
如果矩阵中相应位置的数小于 target，则如果目标值存在，其下标一定大于 mid，因此在下标范围 [mid+1,high] 中继续查找。
如果查找的过程中出现 low>high，则目标值不存在，返回 false。
代码
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int low = 0, high = m * n - 1;while (low <= high) {int mid = low + (high - low) / 2;int row = mid / n, column = mid % n;if (matrix[row][column] == target) {return true;} else if (matrix[row][column] > target) {high = mid - 1;} else {low = mid + 1;}}return false;}
}复杂度分析
-
时间复杂度：O(log(mn))，其中 m 和 n 分别是矩阵 matrix 的行数和列数。矩阵中的元素个数是 mn，二分查找的次数是 O(log(mn))，每次查找的时间是 O(1)，时间复杂度是 O(log(mn))。
-
空间复杂度：O(1)。