74. Search two-dimensional matrix

1、 Title Description

2、 Topic analysis ：

• The integers in each row are arranged in ascending order from left to right .
• The first integer in each row is greater than the last integer in the previous row .

2-1、【 Violence law 】 Arrange topic ideas

1、 You can know that the coordinates are [0][0] Element of point , It must be the smallest element , If it is equal to matrix[0][0] , Then return to true, If (target < matrix[0][0]), That is, it is smaller than the minimum value in the matrix ,  Then return to false

2、 Next, traverse the first element of each line , namely matrix[i][0], If it is equal to the first element of a line , return true, If matrix[i][0] > target, Then terminate the cycle , Jump out of .

3、 At this point, you can get the subscript of the target line

4、 Similarly, traverse each column of elements in the corresponding row , If there are equal, return true, Otherwise false.

  This logic is better , But there is nothing clever , The implementation code is as follows ：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0)   
            return false;
        int row = matrix.length;
        int col = matrix[0].length;
        // Initial verification 
        int minNum = matrix[0][0];
        if(target == minNum) return true;
        else if(target < minNum) return false;

        int aimRow = 1;
        // Traverse the first element of each line , Determine which line the target value is on 
        for(; aimRow < row; aimRow++){
           int rowNum = matrix[aimRow][0];
           if(rowNum == target) return true;
           else if (rowNum > target) break;      
        }
        // At this time, the subscript of the line is determined , Larger than the maximum in the line , Then there is no target value 
        aimRow--;
        if(target > matrix[aimRow][col-1])
            return false;
        
        // Traverse each column of the target row 
        for(int j = 1; j < col; j++){
           int colNum = matrix[aimRow][j];
           if(colNum == target) return true;
        }
        return false;
    }
}

Complexity analysis

Time complexity ：O(n+m), among m  and n  They are the number of rows and columns of the matrix .

Spatial complexity ：O(1).

2-2、 For the above ideas , Code optimization

The idea of solving the above problem is actually to compare the coordinate axis and size logic . At the same time ,【 That's ok 】+【 Column 】 Traverse .

According to the meaning of the question , The two-dimensional array is incremented from left to right , Increase from top to bottom , Therefore, the following conclusions are drawn ：

A number in a column , The number above this number , Are smaller than them ;
A number in a line , The number to the right of the number , Are bigger ;
therefore , The problem solving process is as follows ：

Take the lower left corner of the two-dimensional array as the origin , Establish a rectangular axis .
If the current number is greater than the search number , Move the search up one bit .
If the current number is less than the search number , Move the search one bit to the right .

The code is written as follows ：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // from 【 The lower left corner 】 To traverse the , If target <  Current value  ,rows--,  If  target> Current value ,col++
        int rows = matrix.length - 1, columns = 0;
        while (rows >= 0 && columns < matrix[0].length) {
            int num = matrix[rows][columns];
            if (num == target) {
                return true;
            } else if (num > target) {
                rows--;
            } else {
                columns++;
            }
        }
        return false;
    }
}

Complexity analysis

Time complexity ：O(n+m), among m  and n  They are the number of rows and columns of the matrix .

Spatial complexity ：O(1).

other ： You can also follow the official train of thought , Carry out binary search and other ideas .