“This is the 18th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

1, the title

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

Tip:

  • 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 <= 10^9

2, train of thought

(Monotone scanning)O(n+m)O(n+m) O(n+m)

In m x n matrix, we can find a property: for the number x in the upper right corner of each submatrix, the number to the left of x is less than or equal to x, and the number below x is greater than x.

So we can enumerate from the top right corner of the entire matrix, assuming the current enumeration is x:

  • ifxIs equal to thetarget, it means we found the target value, returntrue;
  • ifxLess thantarget,xEverything on the left-hand side must be less thantarget, we can directly exclude the current whole row;
  • if xIs greater thantarget,xAll the numbers down here must be greater thantarget, we can sort the current whole column directly;

To exclude an entire row is to add one to the x-coordinate of the enumerated point, and to exclude an entire column is to subtract one from the y-coordinate. When we do not find the target value after eliminating the entire matrix, the target value does not exist and returns false.

The specific process is as follows:

  • 1. Initializationi = 0.j = matrix[0].size() - 1.
  • 2, ifmatrix[i][j] == targetTo return totrue.
  • 3, ifmatrix[i][j] < target.i++, exclude a row.
  • 4, ifmatrix[i][j] > target.j--, exclude one column.
  • 5, if out of bounds has not been foundtarget, the returnfalse.

Time complexity analysis: each step will exclude one row or column. The matrix has a total of NNN rows and MMM columns, so n+ Mn + MN + M steps will be carried out at most. So the time is O(n+m)O(n+m)O(n+m).

C++ code

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(! matrix.size() && ! matrix[0].size()) return false;
        int i = 0, j = matrix[0].size() - 1;  // Upper right corner of matrix
        while(i < matrix.size() && j >= 0)
        {
            if(matrix[i][j] == target)  return true;
            else if( matrix[i][j] < target) i++;  // Exclude a row
            else if( matrix[i][j] > target) j--;  // exclude a column
        }
        return false; }};Copy the code

4. Java code

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 0 && matrix[0].length == 0) return false;
        int i = 0, j = matrix[0].length - 1;  // Upper right corner of matrix
        while(i < matrix.length && j >= 0)
        {
            if(matrix[i][j] == target)  return true;
            else if( matrix[i][j] < target) i++;  // Exclude a row
            else if( matrix[i][j] > target) j--;  // exclude a column
        }
        return false; }}Copy the code

Original link: 240. Search two-dimensional matrix II