题目描述
思路:二维矩阵坐标变换 + 二分查找
二维矩阵坐标变换:
只要知道二维数组的的行数m和列数n,二维数组的坐标 (i, j) 可以映射成一维的index = i * n + j;反过来也可以通过一维index反解出二维坐标 i = index / n,j = index % n。(n是列数)
把二维数组matrix的元素访问抽象成在一维数组中访问元素,然后直接施展最基本的二分搜索即可。
方法一:
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) return false;
int m = matrix.length, n = matrix[0].length;
int left = 0, right = m * n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (target == get(matrix, mid)) {
return true;
} else if (target < get(matrix, mid)) {
right = mid - 1;
} else if (target > get(matrix, mid)) {
left = mid + 1;
}
}
return false;
}
// 通过一维坐标访问二维数组中的元素
private int get(int[][] matrix, int index) {
int n = matrix[0].length;
// 计算坐标
int i = index / n, j = index % n;
return matrix[i][j];
}
}
标签:index,matrix,LeetCode74,int,二维,Hot,坐标,length,100
From: https://www.cnblogs.com/keyongkang/p/17918676.html