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)。