This is the 8th day of my participation in the First Challenge 2022. For details: First Challenge 2022.
Reference to Offer 04. Search in a two-dimensional array
Force button topic link
In an N by m two-dimensional array, each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Perform an efficient function that takes such a two-dimensional array and an integer and determines whether the integer is in the array.
Example:
The existing matrix matrix is as follows:
[[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] set target =5To return totrue.Copy the code
Given target = 20, return false.
Limitations:
0 <= n <= 1000
0 <= m <= 1000
Ideas:
First consider brute force cracking. Instead of using the condition that order is known, if there is a target value in a two-dimensional array, the double-layer loop can solve the problem.
Violence law
/ * * *@param {number[][]} matrix
* @param {number} target
* @return {boolean}* /
var findNumberIn2DArray = function(matrix, target) {
let flag = false; // Initialize the flag bit
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] === target) { // If the target value exists in the matrix
flag = true; // Set the flag position to true
break; // End the loop}}}return flag; // Return the flag bit
};
Copy the code
- Time complexity O(n * m).
- Space complexity O(1).
Analysis:
Brute force cracking is a relatively inefficient method, which does not properly take advantage of the characteristics of ascending from left to right and top to bottom. Suitable for unordered or two-dimensional arrays with a small amount of data. When the target value is found, we break the loop and return a flag bit of true, otherwise we need to traverse the entire array to return false.
Pruning method
According to the description, we can prune by comparing the values in the lower left corner. We tentatively set the value in the lower left corner as flag.
flag < target
, we can takeflag
The column is dropped because the value above is definitely smaller;flag > target
, we can takeflag
Drop the row because the value on the right is definitely larger;flag === target
, then find the target value and returntrue
.- Beyond the boundary, meaning not found, return
false
.
The value in the lower left corner is dynamically obtained by matrix[I][j]. According to the characteristics of the two-dimensional array, the value in the lower left corner is the last item of the outer array and the first item of the inner array, so it can be obtained:
/ * * *@param {number[][]} matrix
* @param {number} target
* @return {boolean}* /
var findNumberIn2DArray = function(matrix, target) {
let i = matrix.length - 1; // Get the value in the lower left corner
let j = 0;
while (i >=0 && j < matrix[0].length) { // Loop condition
if (matrix[i][j] < target) j++; // If the current value is less than the target value, it means the target value is on the right
else if (matrix[i][j] > target) i--; // If the current value is greater than the target value, it means the target value is on the top side
else return true; // If equal, there is a target value
}
return false; // If no target value is found at the end of the loop, there is no target value
};
Copy the code
- Time complexity O(n + m).
- Space complexity O(1).
conclusion
Take advantage of the conditions given by the problem and cut out one row or one column at a time to reduce the time complexity from O(n * m) to O(n + m). The two-dimensional array in the problem is similar to a binary search tree, with smaller values in the lower left corner and larger values in the upper right corner. Then prune the operation by comparing the values in the lower left or upper right corner.