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 takeflagThe column is dropped because the value above is definitely smaller;
  • flag > target, we can takeflagDrop 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, returnfalse.

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.