Write an efficient algorithm to search a target value in m x n matrix matrix. The matrix has the following properties:
-
The elements of each row are arranged in ascending order from left to right.
-
The elements of each column are arranged from top to bottom.
Leetcode-cn.com/problems/se…
Example 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 Copy the codeInput: matrix = [,4,7,11,15 [1], [2,5,8,12,19], [3,6,9,16,22], [10,13,14,17,24], [18,21,23,26,30]], target = 5 output: true
Example 2:
1,4,7,11,15 2,5,8,12,19 3,6,9,16,22 10,13,14,17,24,21,23,26,30 18Copy the codeInput: matrix = [,4,7,11,15 [1], [2,5,8,12,19], [3,6,9,16,22], [10,13,14,17,24], [18,21,23,26,30]], target = 20 output: false
Tip:
m == matrix.length n == matrix[i].length 1 <= n, M <= 300-109 <= matix[I][j] <= 109 All elements of each row are arranged in ascending order from left to right and all elements of each column are arranged in ascending order from top to bottom -109 <= target <= 109
Java solution
Ideas:
- Look at the topic is relatively simple, because the matrix left and right up and down are ordered, find out whether the target value exists, it is easy to think of binary search positioning boundary
Start with binary search to find the possible y column (the current column is closest to the column less than target)Locate the target value in that columnY is the largest number of the current XY rectangle when X=Y. Currently, x-1, y-1 is less than target X. If Y is greater than target, then target must be in X. The right and bottom edge of y let’s use binary search to find both sides- The simplest way to do a binary search for each row and column is to write it in an inefficient way
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;
}
// The param data is not ordered
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;
// Use binary lookup to locate possible locations
int startX = 0;
int endX = xLen;
int startY = 0;
int endY = yLen;
int x = -1;
int y = -1;
while (startX <= endX && startY <= endY) {
// Find possible 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) {
/ / can be increased
if (matrix[midY + 1][midX + 1] > target) {/ / find
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 {
/ / in the future
startX = midX + 1;
startY = midY + 1; }}else if (midX < endX) {
if (matrix[midY][midX + 1] > target) {/ / find
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 {
/ / in the future
startX = midX + 1; }}else if (midY < endY) {
/ / can be increased
if (matrix[midY + 1][midX] >= target) {/ / find
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 {
/ / in the future
startY = midY + 1; }}else {
return false; }}else {
if (midX == 0 && midY == 0) {
return false; } endX = midX; endY = midY; }}return false; }}Copy the code
The official solution
Leetcode-cn.com/problems/se…
-
Sequential traversal and sequential binary traversal
Relatively low efficiency
-
Pointer to the shift
The pointer points to the lower-left element and moves based on the target comparison until it is found or out of bounds
This is what I wanted to achieve, but I could not complete it because I always considered the problem of too large matrix and wanted to provide efficiency through binary search