leetcode：1351. 统计有序矩阵中的负数

悠悠 2023-07-25 11:24 6阅读 0赞

# 题目来源 #

*  [1351. 统计有序矩阵中的负数][1351.]

# 题目详情 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_14_color_FFFFFF_t_70_g_se_x_16]

# 题目解析 #

该题目可以分解为求一维数组中比0小的数的个数， 和“荷兰国旗”类似。但是更加简单，因为次数一维数组是有序的。

## 暴力循环破解法 ##

因为数组是递减排列，所以从后向前循环比较好

### c++ ###

int countNegatives(vector<vector<int>>& grid) {
        
        int count = 0;
        for (int i = grid.size() - 1; i >= 0 ; --i) {
        
            for (int j = grid[i].size() - 1; j >= 0 ; --j) {
        
                if (grid[i][j] < 0){
        
                    count++;
                }else{
        
                    break;
                }
            }
        }
    
        return count;
    }

![在这里插入图片描述][affe2b9977f94c90ae46caea4da255b3.png]

### java ###

if (grid == null){
        
                    return 0;
                }
    
                int count = 0;
                for (int i = 0; i < grid.length; i++){
        
                    int[] temp = grid[i];
                    for (int j = temp.length - 1; j > -1 ; j--){
        
                        if (temp[j] >= 0){
        
                            break; // 跳出上一层讯息
                        }else {
        
                            count++;
                        }
                    }
                }
                return  count;

![在这里插入图片描述][20200414204243817.png]

## 利用数组性质\[更快\] ##

根据题目规则 从右上角开始搜索：  
例如二维数组：  
4 3 2 -1  
3 2 1 -1  
1 1 -1 -2  
\-1 -1 -2 -3  
观察可以得出规律如果一个位置为负数，那么它下面的就都为负数。  
如果一个位置为正数，那么这个左边的就都是正数。本题主要是为了统计负数，所以直接跳过即可

### java ###

public static  int countNegatives(int[][] grid) {
        
                if (grid == null){
        
                    return 0;
                }
    
                int count = 0;
                int col = grid.length;
                int line = grid[0].length;
                int x = 0;  //当前行
                int y = grid[0].length - 1; // 当前列
    
              // 从右到左
                while (x < col && y > -1){
        
                    int ele = grid[x][y];
                    if (ele >= 0){
          //如果当前元素大于等于0： 当前元素之前的元素(包括当前元素)全部大于等于0
                        x++; // 进入下一行
                    }else{
         // 当前当前元素小于0，那么当前元素下面的元素全部小于0
                        // 当前元素下面有多少的元素 =  col - x
                        count = count + col - x;
                        y--;
                    }
                }
    
                return  count;
          }

![在这里插入图片描述][20200415094703364.png]

### c++ ###

class Solution {
        
    public:
    int countNegatives(vector<vector<int>>& grid) {
        
        int count = 0;
        int col = grid.size(); 
        int line = grid[0].size();
        int x = 0; 
        int y = line - 1;
        int data ;
        while (x < col && y > -1){
        
            data = grid[x][y];
            if (data < 0){
        
                count += (col - x);
                y--;
            }else{
        
                x++;
            }
        }
    
        return count;
    }
    };

![在这里插入图片描述][811e4bbd1d61430b9b821c03cac5fbdd.png]

[1351.]: https://leetcode-cn.com/problems/count-negative-numbers-in-a-sorted-matrix/submissions/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20230528/49f94d71b9a44ae9ab9787f7eb96f6a2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20230528/0d3684a270b24af7a525e672e692c4a9.png
[affe2b9977f94c90ae46caea4da255b3.png]: /images/20230528/a8fed8fa3b8c4d2ea86e8638496c1522.png
[20200414204243817.png]: /images/20230528/b488585250d941eabb035ec0934c2124.png
[20200415094703364.png]: /images/20230528/3f508720d6dc44c6b9829a08749f7a1c.png
[811e4bbd1d61430b9b821c03cac5fbdd.png]: /images/20230528/db90e7e4360c42bb803d7abf0b1d39da.png