Easy

题目描述

给你一个 m x n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。请你统计并返回 grid 中负数的数目。

示例 1：

输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出：8
解释：矩阵中共有 8 个负数。

示例 2：

输入：grid = [[3,2],[1,0]]
输出：0

提示：

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

**进阶：**你可以设计一个时间复杂度为 O(n + m) 的解决方案吗？

解题思路

这道题有三种主要解法：

方法一：暴力遍历 最直观的方法是遍历整个矩阵，统计负数个数。时间复杂度为 O(m×n)。

方法二：二分查找优化 由于每行都是非递增排序的，可以对每一行使用二分查找来找到第一个负数的位置。这样时间复杂度为 O(m×log n)。

方法三：从右上角开始遍历（推荐） 利用矩阵的性质：行和列都是非递增的。从右上角开始，如果当前元素为负数，则该列下方所有元素都是负数；如果为非负数，则向左移动。这样可以在 O(m+n) 时间内解决问题。

具体思路：从右上角 (0, n-1) 开始，如果 grid[i][j] < 0，说明第 j 列从第 i 行开始往下都是负数，计数器加上 (m-i)，然后向左移动；如果 grid[i][j] >= 0，向下移动。

代码实现

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int count = 0;
        int i = 0, j = n - 1;
        
        while (i < m && j >= 0) {
            if (grid[i][j] < 0) {
                count += m - i;
                j--;
            } else {
                i++;
            }
        }
        
        return count;
    }
};

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        count = 0
        i, j = 0, n - 1
        
        while i < m and j >= 0:
            if grid[i][j] < 0:
                count += m - i
                j -= 1
            else:
                i += 1
        
        return count

public class Solution {
    public int CountNegatives(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int count = 0;
        int i = 0, j = n - 1;
        
        while (i < m && j >= 0) {
            if (grid[i][j] < 0) {
                count += m - i;
                j--;
            } else {
                i++;
            }
        }
        
        return count;
    }
}

var countNegatives = function(grid) {
    const m = grid.length, n = grid[0].length;
    let count = 0;
    let i = 0, j = n - 1;
    
    while (i < m && j >= 0) {
        if (grid[i][j] < 0) {
            count += m - i;
            j--;
        } else {
            i++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
从右上角遍历O(m + n)O(1)
二分查找O(m log n)O(1)
暴力遍历O(m × n)O(1)

相关题目