This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details
Topic describes
Search two dimensional matrix
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.
Example 1:
Input: 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: trueCopy the code
Example 2:
Input: 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: falseCopy the code
prompt
- m == matrix.length
- n == matrix[i].length
- 1 <= n, m <= 300
- – 109 < =
matix[i][j]
< = 109 - All elements in each row are arranged in ascending order from left to right
- All elements in each column are arranged in ascending order from top to bottom
- -109 <= target <= 109
Thought analysis
First of all, brute force cracking, but without the word efficient, we can choose dichotomy for optimization, because it’s already sorted matrix, we can traverse the diagonal of the matrix,
The code shown
Solution 1: Brute force cracking, time complexity O(mn){O(mn)}O(mn), space complexity O(1){O(1)}O(1).
public boolean searchMatrix(int[][] matrix, int target) {
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;
}
Copy the code
Solution 2: binary search, the matrix has been sorted, we need to use binary search to speed up our algorithm. Time complexity O(LG (n!) ){O(lg(n!) )}O(lg(n!) ), space complexity O(1){O(1)}O(1).
private 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 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;
}
Copy the code
Method 3: time complexity O (m + n) (m + n)} {O O (m + n), space complexity O (1) (1)} {O O (1).
public boolean searchMatrix(int[][] matrix, int target) {
// start our "pointer" in the bottom-left
int row = matrix.length-1;
int col = 0;
while (row >= 0 && col < matrix[0].length) {
if (matrix[row][col] > target) {
row--;
} else if (matrix[row][col] < target) {
col++;
} else { // found it
return true; }}return false;
}
Copy the code