文章目录
- 题目
- 标题和出处
- 难度
- 题目描述
- 要求
- 示例
- 数据范围
- 解法
- 思路和算法
- 代码
- 复杂度分析
题目
标题和出处
标题：搜索二维矩阵
出处：74. 搜索二维矩阵
难度
3 级
题目描述
要求
给定一个 m × n \texttt{m} \times \texttt{n} m×n 的整数矩阵 matrix \texttt{matrix} matrix，该矩阵具有如下特性：
- 每行中的整数从左到右按升序排序。
- 每行的第一个整数大于前一行的最后一个整数。
给定一个整数 target \texttt{target} target，如果 target \texttt{target} target 在 matrix \texttt{matrix} matrix 中，返回 true \texttt{true} true，否则返回 false \texttt{false} false。
要求时间复杂度是 O(log (m × n)) \texttt{O(log (m} \times \texttt{n))} O(log (m×n))。
示例
示例 1：
输入： matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 \texttt{matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3} matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出： true \texttt{true} true
示例 2：
输入： matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 \texttt{matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13} matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出： false \texttt{false} false
数据范围
- m = matrix.length \texttt{m} = \texttt{matrix.length} m=matrix.length
- n = matrix[i].length \texttt{n} = \texttt{matrix[i].length} n=matrix[i].length
- 1 ≤ m, n ≤ 100 \texttt{1} \le \texttt{m, n} \le \texttt{100} 1≤m, n≤100
- -10 4 ≤ matrix[i][j], target ≤ 10 4 \texttt{-10}^\texttt{4} \le \texttt{matrix[i][j], target} \le \texttt{10}^\texttt{4} -104≤matrix[i][j], target≤104
解法
思路和算法
由于给定的矩阵满足每行升序排序，且每行的第一个整数大于前一行的最后一个整数，因此如果将矩阵的每一行拼接到前一行的末尾，可以得到一个升序数组， m m m 行 n n n 列的矩阵可以转换成长度为 m × n m \times n m×n 的升序数组。矩阵中的每个位置可以和升序数组中的下标转换：
-
当 0 ≤ i < m 0 \le i < m 0≤i<m 且 0 ≤ j < n 0 \le j < n 0≤j<n 时，矩阵的第 i i i 行第 j j j 列等价于升序数组的下标 i × n + j i \times n + j i×n+j；
-
当 0 ≤ index < m × n 0 \le \textit{index} < m \times n 0≤index<m×n 时，升序数组的下标 index \textit{index} index 等价于矩阵的第 ⌊ index n ⌋ \Big\lfloor \dfrac{\textit{index}}{n} \Big\rfloor ⌊nindex⌋ 行第 index m o d n \textit{index} \bmod n indexmodn 列。
为了判断矩阵中是否存在目标值，可以在矩阵转换成的升序数组中二分查找。
用 low \textit{low} low 和 high \textit{high} high 分别表示二分查找的下标范围的下界和上界，初始时 low = 0 \textit{low} = 0 low=0， high = m × n − 1 \textit{high} = m \times n - 1 high=m×n−1。每次查找时，取 mid \textit{mid} mid 为 low \textit{low} low 和 high \textit{high} high 的平均数向下取整，计算下标 mid \textit{mid} mid 对应的矩阵行下标和列下标，判断矩阵中的相应位置的数和目标值的大小关系，调整查找的下标范围。
-
如果矩阵中相应位置的数等于 target \textit{target} target，则找到目标值，返回 true \text{true} true。
-
如果矩阵中相应位置的数大于 target \textit{target} target，则如果目标值存在，其下标一定小于 mid \textit{mid} mid，因此在下标范围 [ low , mid − 1 ] [\textit{low}, \textit{mid} - 1] [low,mid−1] 中继续查找。
-
如果矩阵中相应位置的数小于 target \textit{target} target，则如果目标值存在，其下标一定大于 mid \textit{mid} mid，因此在下标范围 [ mid + 1 , high ] [\textit{mid} + 1, \textit{high}] [mid+1,high] 中继续查找。
如果查找的过程中出现 low > high \textit{low} > \textit{high} low>high，则目标值不存在，返回 false \text{false} 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 ( m × n ) ) O(\log (m \times n)) O(log(m×n))，其中 m m m 和 n n n 分别是矩阵 matrix \textit{matrix} matrix 的行数和列数。矩阵中的元素个数是 m × n m \times n m×n，二分查找的次数是 O ( log ( m × n ) ) O(\log (m \times n)) O(log(m×n))，每次查找的时间是 O ( 1 ) O(1) O(1)，时间复杂度是 O ( log ( m × n ) ) O(\log (m \times n)) O(log(m×n))。
-
空间复杂度： O ( 1 ) O(1) O(1)。