Title link: Reference Offer 04. Search in a two-dimensional array

Title description:

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]]Copy the code
Given target = 5, return true. Given target = 20, return false.Copy the code
Limitations:
0 <= n <= 1000

0 <= m <= 1000
Copy the code

Directions: For this part,

This problem is a classic matrix problem. Through observation, we can find that the matrix shown in the problem has such a characteristic: extreme values are all in the four corners.

Just like the matrix in the example, the upper left corner is the maximum and the lower right corner is the minimum.

Let’s start with:

Start at the bottom left, and use the increasing relationship given by the matrix, if greater, go to the right, if less, go up, and return false if it exceeds the length of the matrix.

Solution implementation:

  1. The first step is to initialize an array of flags that record all the traversed elements.
  2. Used values need to be formatted to indicate that they have been traversed, and then modified after traversing.
  3. Finally, make sure to break in time, otherwise you will time out.
func findNumberIn2DArray(matrix [][]int, J :=0 for I >-1{if j<len(matrix[I]){if j<len(matrix[I]){if j<len(matrix[I]){if If target>matrix[I][j]{j++ // if target>matrix[I][j]{j++ // if target>matrix[I][j]{j++ // if target>matrix[I][j] Target ==matrix[I][j]{return true}}else{// Return false return false}Copy the code

Conclusion:

On the whole, it is not difficult. After understanding the idea, it is also easy to realize it by yourself. It belongs to the topic that will be impressed once you have done it.

Another idea is to use the SeachInts method under the Sort package and iterate over a set of slices. However, this kind of ready-made API call is actually not conducive to the exercise of our algorithm thinking, I will not expand on that, interested can go to research.