Q: which son of Kangxi do programmers hate most?
A. There is no rest.
Today I still share with you a frequent interview topic. Not much. Let’s see.
01. Examples of topics
This topic is very high frequency! Seems to be looking at matrix search, actually has nothing to do with the matrix….
| Problem 74: Search for a two-dimensional matrix |
|---|
| Write an efficient algorithm to determine whether there is a target value in an M x n matrix. |
The matrix has the following characteristics:
- The integers in each row are arranged in ascending order from left to right.
- The first integer in each line is greater than the last integer in the previous line.
Example 1:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20].
[50] 23, 30, 34,
]
target = 3
Output:true
Copy the codeExample 2:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20].
[50] 23, 30, 34,
]
target = 13
Output:false
Copy the code
The question itself is relatively easy to understand, there is not much additional.
02, Solution analysis
To put it bluntly, this is a problem that examines dichotomy.
The most important things are the two conditions given in the question:
-
The first integer in each line is greater than the last integer in the previous line.
-
The integers in each row are arranged in ascending order from left to right.
The first condition means that a binary search can determine which row;
The second condition means that a binary search can be performed in the row to determine which element;
How do you use binary lookup to find which row? You just need an upper and lower boundary, and then you take the maximum value of the middle row and compare it with the target value each time.
//java
public int getRow(int[][] matrix, int target) {
// Dichotomy to find the row where target is located
int top = 0, bottom = matrix.length - 1;
int col = matrix[0].length - 1;
while (top < bottom) {
int mid = (top + bottom) / 2;
if (matrix[mid][col] < target)
top = mid + 1;
else
bottom = mid;
}
return top;
}
Copy the codeOnce the row is found, it is indistinguishable from a normal binary search:
//java
public boolean find(int[] data, int target) {
// Binary search
int l = 0, r = data.length - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (data[mid] == target)
return true;
else if (data[mid] < target)
l = mid + 1;
else
r = mid - 1;
}
return false;
}
Copy the codeThen put the code back together:
//java
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length < 1) return false;
int row = getRow(matrix, target);
return find(matrix[row], target);
}
public int getRow(int[][] matrix, int target) {
int top = 0, bottom = matrix.length - 1;
int col = matrix[0].length - 1;
while (top < bottom) {
int mid = (top + bottom) / 2;
if (matrix[mid][col] < target)
top = mid + 1;
else
bottom = mid;
}
return top;
}
public boolean find(int[] data, int target) {
int l = 0, r = data.length - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (data[mid] == target)
return true;
else if (data[mid] < target)
l = mid + 1;
else
r = mid - 1;
}
return false;
}
}
Copy the code03. Tips
The Fibonacci sequence is introduced with the example of rabbit reproduction, so it is also called “rabbit sequence”. A sequence in which, starting with the third term, each term is equal to the sum of the first two terms.
1，1，2，3，5，8，13，21，34，55，89，144……..
That’s the end of today’s topic, have you learned? Leave your thoughts in the comments section!
I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download
