LeetCode（Binary Search)1351. Count Negative Numbers in a Sorted Matrix

短命女 2023-09-25 23:37 32阅读 0赞

# 1.问题 #

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

Example 1:

> Input: grid = \[\[4,3,2,-1\],\[3,2,1,-1\],\[1,1,-1,-2\],\[-1,-1,-2,-3\]\]  
> Output: 8  
> Explanation: There are 8 negatives number in the matrix.

Example 2:

> Input: grid = \[\[3,2\],\[1,0\]\]  
> Output: 0

Constraints:

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

# 2. 解题思路 #

## 方法1： ##

> 使用了暴力枚举法，遍历整个矩阵并统计负数的数量。  
> 矩阵的行数和列数，因此在矩阵较大时会比较慢。  
> 另外，由于题目给定的矩阵是按非递增顺序排好序的，因此可以利用这一特点，使用更快的方法来解决本题。

## 方法2： ##

> 1.由于矩阵已按非递增顺序排好序，因此我们可以从右上角开始遍历矩阵  
> 2.如果当前元素是负数，则当前列及其下面的所有元素都是负数，因此负数数量加上当前列下面的元素个数（即行数减去当前行的行坐标），并向左移动一列继续遍历  
> 3.否则向下移动一行继续遍历。  
> 4.当遍历到左下角时，即统计出所有负数的数量。

## 方法3： ##

> 可以利用矩阵按非递增顺序排好序的特点，采用二分查找的方法来解决本题。  
> 由于每一行都是按非递增顺序排好序的  
> 1.在每一行中使用二分查找找到第一个负数出现的位置  
> 2.然后将该位置及其右边的元素都是负数，负数数量加上该行中右边元素的个数  
> 3.最后将所有行中的负数数量加起来即为整个矩阵中负数的数量。

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public int countNegatives(int[][] grid) {
        
            int sum=0; // 统计负数数量的变量，初始化为0
            for (int i = 0; i < grid.length; i++) {
         // 遍历矩阵的每一行
               int[] data= grid[i]; // 获取当前行的数据
                for (int j = 0; j < data.length; j++) {
         // 遍历当前行的每一个元素
                    if(data[j]<0){
         // 如果当前元素是负数
                            sum++; // 将负数数量加1
                    }
                }
            }
            return sum; // 返回负数数量
        }
    }

## 代码2： ##

class Solution {
        
        public int countNegatives(int[][] grid) {
        
            int count = 0; // 统计负数数量的变量，初始化为0
            int row = grid.length; // 获取矩阵的行数
            int col = grid[0].length; // 获取矩阵的列数
    
            // 从右上角开始遍历矩阵，因为右上角是最后一个负数出现的地方
            int i = 0; // 行坐标
            int j = col - 1; // 列坐标
            while (i < row && j >= 0) {
         // 只要还没有遍历完整个矩阵就继续遍历
                if (grid[i][j] < 0) {
         // 如果当前元素是负数
                    count += row - i; // 则当前列及其下面的所有元素都是负数，累加数量
                    j--; // 左移一列，继续遍历
                } else {
         // 如果当前元素不是负数
                    i++; // 下移一行，继续遍历
                }
            }
    
            return count; // 返回负数数量
        }
    }

## 代码3： ##

class Solution {
        
        public int countNegatives(int[][] grid) {
        
            int count = 0; // 统计负数数量的变量，初始化为0
            for (int[] row : grid) {
         // 遍历矩阵的每一行
                int left = 0; // 左边界
                int right = row.length - 1; // 右边界
                int index = -1; // 记录第一个负数出现的位置，初始化为-1
                while (left <= right) {
         // 只要左边界小于等于右边界就继续查找
                    int mid = left + (right - left) / 2; // 中间位置
                    if (row[mid] < 0) {
         // 如果当前元素是负数
                        index = mid; // 记录该位置
                        right = mid - 1; // 向左边继续查找
                    } else {
         // 如果当前元素不是负数
                        left = mid + 1; // 向右边继续查找
                    }
                }
                if (index != -1) {
         // 如果该行中有负数
                    count += row.length - index; // 将负数数量加上该行右边元素的个数
                }
            }
            return count; // 返回负数数量
        }
    }

> 该代码和前面给出的二分查找方法类似，但是只需要找到第一个负数出现的位置即可，无需继续向左查找。因此，该代码的时间复杂度为 O ( m log ⁡ n ) O(m\\log n) O(mlogn)，其中 m m m和 n n n分别是矩阵的行数和列数。与前面的二分查找方法相比，该方法的空间复杂度更低，只需要使用常数级别的空间来存储一些变量。

public int countNegatives(int[][] grid) {
        
        int rows = grid.length, cols = grid[0].length; 
        int res = 0, lastNeg = cols - 1;
        for (int row = 0; row < rows; row++) {
        
            // 如果当前行的第一个元素就是负数，则该行所有元素都是负数，直接累加
            if (grid[row][0] < 0) {
        
                res += cols;
                continue;
            }
            // 如果当前行的最后一个元素是正数，则该行没有负数，跳过
            if (grid[row][cols - 1] > 0)
                continue;
            // 如果当前行中有正数和负数，则需要二分查找找到第一个负数的位置
            int l = 0, r = lastNeg;
            while (l <= r) {
        
                int m = l + (r - l) / 2;
                if (grid[row][m] < 0) {
        
                    r = m - 1;
                } else {
        
                    l = m + 1;
                }
            }
            // 将该行中负数的数量加上
            res += (cols - l);
            lastNeg = l; // 更新最后一个负数的位置
        }
        return res; // 返回负数的数量
    }