LeetCode 74 - Search a 2D Matrix

作者 QIFAN 日期 2017-01-19
LeetCode 74 - Search a 2D Matrix

原题链接: 74. Search a 2D Matrix


题干

给定一个矩阵,它的每一行从左到右依次增大,且每一行的第一个大于上一行的最后一个。给定一个 target ,返回是否存在。

思路

折叠起来的二叉查找。
核心在如果将一维数组的位置投射到二维矩阵中。

假设一个 m * n 的矩阵 matrix 一行接一行铺开成一维数组 array ,其长度 array.length = m \* narray[i] 对应的是 matrix[i / n][i % n]

空间复杂度为 $O(1)$ ,时间复杂度为 $O(log(mn))$ 。

代码:

public boolean searchMatrix(int[][] matrix, int target) {
int M = matrix.length;
if (M == 0) {
return false;
}
int N = matrix[0].length;
int TOTAL = M * N;
return binaryMatrixSearch(matrix, target, 0, TOTAL - 1);
}
private boolean binaryMatrixSearch(int[][] matrix, int target, int lo, int hi) {
if (lo > hi) {
return false;
}
int mid = lo + (hi - lo) / 2;
int midRow = mid / matrix[0].length;
int midCol = mid % matrix[0].length;
if (matrix[midRow][midCol] == target) {
return true;
}
if (matrix[midRow][midCol] > target) {
return binaryMatrixSearch(matrix, target, lo, mid - 1);
}
return binaryMatrixSearch(matrix, target, mid + 1, hi);
}