Day85 搜索二维矩阵 II
2021-04-22 本文已影响0人
Shimmer_
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
-
每行的元素从左到右升序排列。
-
每列的元素从上到下升序排列。
示例1：
1, 4, 7, 11, 15 2, 5, 8, 12, 19 3, 6, 9, 16, 22 10, 13, 14, 17, 24 18, 21, 23, 26, 30输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
示例2：
1,4,7,11,15 2,5,8,12,19 3,6,9,16,22 10,13,14,17,24 18,21,23,26,30输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false
提示：
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matix[i][j] <= 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-109 <= target <= 109
Java解法
思路：
- 看题目比较简单，因为矩阵左右上下都有序，找出目标值是否存在，很容易想到二分查找定位边界
先通过二分查找找到可能存在的y列（当前列最接近小于target的列）再在该列找到目标值
踩坑，Y列有序不是强关联因为矩阵是左顶角到右底角有序增大，可以考虑同时二分查找X，Y当X=Y时是当前xy矩形最大的数，当前x-1，y-1 小于target x，y大于target时，那target必在x，y右、下底边上在用二分查找 对这两边进行查找- 又陷入死角了，参考官方解：采用 最简单的方式，对每行每列进行二分查找：比较低效率的写法
package sj.shimmer.algorithm.m4_2021;
/**
* Created by SJ on 2021/4/22.
*/
class D85 {
public static void main(String[] args) {
int[][] matrix = {
{1, 4, 7, 11, 15},
{2, 5, 8, 12, 19},
{3, 6, 9, 16, 22},
{10, 13, 14, 17, 24},
{18, 21, 23, 26, 30},
};
int[][] matrix2 = {
{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20},
{21, 22, 23, 24, 25},
};
int[][] matrix3 = {
{1, 4, 7, 11, 15},
{2, 5, 8, 12, 19},
{3, 6, 9, 16, 22},
{10, 13, 14, 17, 24},
{18, 21, 23, 26, 30},
};
int[][] matrix4 = {
{1, 3, 5},
};
int[][] matrix5 = {
{1, 4},
{2, 5},
};
int[][] matrix6 = {
{-1, 3},
};
// System.out.println(searchMatrix(matrix, 5));
// System.out.println(searchMatrix(matrix, 20));
// System.out.println(searchMatrix(matrix, 30));
// System.out.println(searchMatrix(matrix2, 19));
// System.out.println(searchMatrix(matrix3, 5));
// System.out.println(searchMatrix(matrix4, 1));
// System.out.println(searchMatrix(matrix5, 2));
// System.out.println(searchMatrix(matrix6, 3));
System.out.println(searchMatrix(matrix2, 15));
}
private static boolean binarySearch(int[][] matrix, int target, int start, boolean vertical) {
int lo = start;
int hi = vertical ? matrix[0].length - 1 : matrix.length - 1;
while (hi >= lo) {
int mid = (lo + hi) / 2;
if (vertical) { // searching a column
if (matrix[start][mid] < target) {
lo = mid + 1;
} else if (matrix[start][mid] > target) {
hi = mid - 1;
} else {
return true;
}
} else { // searching a row
if (matrix[mid][start] < target) {
lo = mid + 1;
} else if (matrix[mid][start] > target) {
hi = mid - 1;
} else {
return true;
}
}
}
return false;
}
public static boolean searchMatrix(int[][] matrix, int target) {
// an empty matrix obviously does not contain `target`
if (matrix == null || matrix.length == 0) {
return false;
}
// iterate over matrix diagonals
int shorterDim = Math.min(matrix.length, matrix[0].length);
for (int i = 0; i < shorterDim; i++) {
boolean verticalFound = binarySearch(matrix, target, i, true);
boolean horizontalFound = binarySearch(matrix, target, i, false);
if (verticalFound || horizontalFound) {
return true;
}
}
return false;
}
//忽略了 对位数据无有序关系
public static boolean searchMatrix2(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return false;
}
int yLen = matrix.length - 1;
int xLen = matrix[0].length - 1;
//通过二分查找定位可能存在的位置
int startX = 0;
int endX = xLen;
int startY = 0;
int endY = yLen;
int x = -1;
int y = -1;
while (startX <= endX && startY <= endY) {
//找到可能存在的Y
int midX = (startX + endX) / 2;
int midY = (startY + endY) / 2;
if (matrix[midY][midX] == target) {
return true;
} else if (matrix[midY][midX] < target) {
if (midX < endX && midY < endY) {
//可增大
if (matrix[midY + 1][midX + 1] > target) {//找到
for (int i = midX; i >= 0; i--) {
if (matrix[midY + 1][i] == target) {
return true;
}
}
for (int i = midY; i >= 0; i--) {
if (matrix[i][midX + 1] == target) {
return true;
}
}
return false;
} else if (matrix[midY + 1][midX + 1] == target) {
return true;
} else {
//往后找
startX = midX + 1;
startY = midY + 1;
}
} else if (midX < endX) {
if (matrix[midY][midX + 1] > target) {//找到
for (int i = midY; i >= 0; i--) {
if (matrix[i][midX + 1] == target) {
return true;
}
}
return false;
} else if (matrix[midY][midX + 1] == target) {
return true;
} else {
//往后找
startX = midX + 1;
}
} else if (midY < endY) {
//可增大
if (matrix[midY + 1][midX] >= target) {//找到
for (int i = midX; i > 0; i--) {
if (matrix[midY + 1][i] == target) {
return true;
}
}
return false;
} else if (matrix[midY + 1][midX] == target) {
return true;
} else {
//往后找
startY = midY + 1;
}
} else {
return false;
}
} else {
if (midX == 0 && midY == 0) {
return false;
}
endX = midX;
endY = midY;
}
}
return false;
}
}
image
官方解
-
依次遍历及依次二分遍历
比较低下的效率
-
指针移位
指针指向左下角元素，根据target的比较进行移动 直到找到或越界
这是我想达到的效果，但是因为一直考虑到矩阵过大的问题，想通过二分查找提供效率，导致不能完成
