编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true
示例 2:
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出:false
提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/search-a-2d-matrix
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
感谢
御三五
的详细解法
【坐标轴法】搜索二维矩阵
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
// return searchMatrixI(matrix, target);
// return searchMatrixII(matrix, target);
return searchMatrixIII(matrix, target);
}
//方法三:坐标轴法
//根据题意可知,二维数组从左往右递增,从上往下递增,因此可以得出结论:
//1.某列的某个数字,该数之下的数字都比其大
//2.某行的某个数字,该数之左的数字都比其小
//因此以二维数组的右上角为坐标原点,建立直角坐标轴,若当前数字小于要查找的数,则往下移动一位;若当前数字大于要查找的数,则往左移动一位
//时间复杂度O(m+n),空间复杂度O(1)
private boolean searchMatrixIII(int[][] matrix, int target) {
int row = 0;
int column = matrix[0].length - 1;
while (row < matrix.length && column >= 0) {
int num = matrix[row][column];
if (num < target) {
row++;
} else if (num > target) {
column--;
} else {
return true;
}
}
return false;
}
//方法二:二分法
//将二维矩阵的索引转换为一维矩阵索引,由题意可知在绝对索引上数字递增,因此可以使用二分查找法
//假设二维矩阵是m行n列,(i,j)的绝对索引idx,求得i=idx / n, j=idx % n
//时间复杂度O(logmn),空间复杂度O(1)
private boolean searchMatrixII(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int left = 0;
int right = m * n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int x = matrix[mid / n][mid % n];
if (x < target) {
left = mid + 1;
} else if (x > target) {
right = mid - 1;
} else {
return true;
}
}
return false;
}
//方法一:暴力解法
//时间复杂度O(m*n),空间复杂度O(1)
private boolean searchMatrixI(int[][] matrix, int target) {
if (matrix == null || matrix[0] == null) {
return false;
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == target) {
return true;
}
}
}
return false;
}
}
版权声明:本文为Bonbon_wen原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。