Leetcode 1351. Negative numbers in statistical ordered matrices

1351、 Count the negative numbers in an ordered matrix

1） Title Description

To give you one m * n Matrix grid, The elements of a matrix, whether by row or column , All in non increasing order . Please count and return grid in negative Number of .

Example 1：

 Input ：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
 Output ：8
 explain ： Common matrix  8  Negative numbers .

Example 2：

 Input ：grid = [[3,2],[1,0]]
 Output ：0

Tips ：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100

2） analysis

Traverse .

• Traverse to the first element of each line , Judge positive and negative , If negative , The result directly adds the product of the length of one line and the number of remaining lines , Exit traversal ;
• If the first element of the current line is nonnegative , Traverse the row , Judge the positive and negative of each element , If negative , The result is added with the number of elements remaining in the current line , Exit the traversal of the current line .

Traveled through , Intra bank dichotomy .

• Traverse to the first element of each line , Judge positive and negative , If negative , The result directly adds the product of the length of one line and the number of remaining lines , Exit traversal ;
• If the first element of the current line is nonnegative , Find the position of the first negative number by two points , The result is added with the number of elements remaining in the current line , Exit the search of the current line .

3）C++ Code

Traverse

class Solution {
    
public:
    int countNegatives(vector<vector<int>>& grid) {
    
        int res=0;
        for(int i=0;i<grid.size();i++){
    
            if(grid[i][0]>=0){
    
                for(int j=0;j<grid[0].size();j++){
    
                    if(grid[i][j]<0){
    
                        res+=grid[0].size()-j;
                        break;
                    }
                }
            }
            else{
    
                res+=grid[0].size()*(grid.size()-i);
                break;
            }
        }
        return res;
    }
};

Traveled through , Intra bank dichotomy .

class Solution {
    
public:
    int countNegatives(vector<vector<int>>& grid) {
    
        int res=0;
        int m=grid.size();
        int n=grid[0].size();
        for(int i=0;i<m;i++){
    
            if(grid[i][0]>=0){
    
                if(grid[i][n-1]>=0)
                    continue;
                else{
    
                    int left=0;
                    int right=n-1;
                    while(left<=right){
    
                        int mid=(left+right)/2;
                        if(grid[i][mid]>=0)
                            left=mid+1;
                        else
                            right=mid-1;
                    }
                    res+=grid[i][left]<0?n-left:0;
                }
            }
            else{
    
                res+=n*(m-i);
                break;
            }
        }
        return res;
    }
};