问题背景
给你一个满足下述两条属性的 m × n m \times n m×n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 t a r g e t target target，如果 t a r g e t target target 在矩阵中，返回 t r u e true true；否则，返回 f a l s e false false。
数据约束
- m = m a t r i x . l e n g t h m = matrix.length m=matrix.length
- n = m a t r i x [ i ] . l e n g t h n = matrix[i].length n=matrix[i].length
- 1 ≤ m , n ≤ 100 1 \le m, n \le 100 1≤m,n≤100
- − 1 0 4 ≤ m a t r i x [ i ] [ j ] , t a r g e t ≤ 1 0 4 -10 ^ 4 \le matrix[i][j], target \le 10 ^ 4 −104≤matrix[i][j],target≤104
解题过程
题目保证整个矩阵中的元素从上到下从左到右依次递增，也就是可以展开成一个递增的一维数组，可以用下标映射的方式，在这个虚拟的一维矩阵中进行二分搜索，时间复杂度为 O ( l o g ( m n ) ) O(log(mn)) O(log(mn))。
还可以用排除法，参考 搜索二维矩阵 II。从矩阵的右上角开始，每次比较能够去掉一行或一列，相当于查找抽象的二叉搜索树，时间复杂度大致在 O ( m + n ) O(m + n) O(m+n) 这个量级。
具体实现
整体二分
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int left = 0, right = m * n;while(left < right) {int mid = left + ((right - left) >>> 1);int cur = matrix[mid / n][mid % n];if(cur == target) {return true;}if(cur < target) {left = mid + 1;} else {right = mid;}}return false;}
}
查找抽象二叉搜索树
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int i = 0;int j = matrix[0].length - 1;while(i < matrix.length && j >= 0) {int cur = matrix[i][j];if(cur == target) {return true;}if(cur < target) {i++;} else {j--;}}return false;}
}