LC 1351.Count Negative Numbers in a Sorted Matrix

题目描述

这是 LeetCode 上的 1351. 统计有序矩阵中的负数 ，难度为简单。

给你一个 m * 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) 的解决方案吗？

解答

方法一：暴力

最简单的方法就是遍历一遍整个矩阵，统计负数的数量。

class Solution {
    public int countNegatives(int[][] grid) {
        int count = 0;
        for (int i = grid.length - 1; i >= 0; --i) {
            for (int j = grid[0].length - 1; j >= 0; --j) {
                if (grid[i][j] < 0) {
                    ++count;
                }
            }
        }
        return count;
    }
}

• 时间复杂度：\(O(mn)\)，其中 m 表示矩阵的列数， n 表示矩阵的行数，即整个矩阵的元素总个数。

• 空间复杂度：\(O(1)\)，用了一个 count 计数。

方法二：二分查找

由于题目中提到矩阵的行和列都是按照非递增的顺序排列，所以可以利用这个性质来优化暴力解法。通过二分查找来寻找每一行从前往后的第一个出现的负数，那么这个位置之后的数都是负数，所以可以直接统计。

1. 遍历矩阵的每一行。
2. 二分查找到该行从前往后的第一个负数，考虑第 i 行，记第一个负数的位置为 \(pos_i\) ，那么第 i 行 \([pos_i, m - 1]\) 中的所有数都是负数，所以这一行的负数个数为 \(m - 1 - pos_i + 1 = m - pos_i\) 。
3. 所以最后的数量就是 \(\sum_{i = 0}^{n - 1} (m - pos_i)\) 。

class Solution {
    public int countNegatives(int[][] grid) {
        int num = 0;
        for (var row : grid) {
            int l = 0, r = grid[0].length - 1, pos = -1;
            while (l <= r) { // 要注意边界条件
                int mid = l + ((r - l) >> 1); // 这个位操作就是对2取余的操作，但是效率更高
                if (row[mid] < 0) {
                    pos = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            if (pos >= 0) { // 如果是C++判断条件可以写成~pos
                num += row.length - pos;
            }
        }
        return num;
    }
}

• 时间复杂度：\(O(n \log m)\)，由于二分查找每一行的时间复杂度为 \(\log m\) ，而矩阵共 n 行，所以时间复杂度为 \(n \log m\)。

• 空间复杂度：\(O(1)\)，只使用了常数个变量。

方法三：倒序遍历

在二分查找中我们只使用了每行的数是非递增的条件，但是实际上这个矩阵的行和列都是非递增的，所以可以进一步优化。由于矩阵的列也是非递增的，所以对于第 i 行设第一个负数出现的位置为 \(pos_i\) ，我们有如下的不等式： \[ pos_0 \geq pos_1 \geq pos_2 \geq \ldots \geq pos_i \geq \ldots \geq pos_{n - 1} \] 因此，在遍历的时候我们可以选择倒序遍历（正序遍历也可以，思路是一样的），用 pre 来存储上一次遍历第 i + 1 行时从前往后第一个出现的负数的位置 \(pos_{i + 1}\) （即\(pos_{i + 1} = pre\)） ，当遍历第 i 行的时候，从前往后出现的第一个负数的位置一定在 [pre, n - 1] 的范围内（其中 n 为每行的元素个数），由此可以让第 i 行的左边界变为 pre ，从而缩小二分查找的范围，进而优化时间复杂度。（感兴趣的也可以使用分治法解决，是类似的思路，可以参考1351-LeetCode官方解法）

class Solution {
    public int countNegatives(int[][] grid) {
        int num = 0, pre = 0; // 用pre而不是一个数组来存储前一行的位置，因为每次只需要前一行的位置即可
        for (int i = grid.length - 1; i >= 0; --i) {
            int l = pre, r = grid[0].length - 1, pos = -1;
            while (l <= r) {
                int mid = l + ((r - l) >> 1);
                if (grid[i][mid] < 0) {
                    pos = mid;
                    pre = mid; // 记录当前行第一个负数的位置
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            if (pos >= 0) {
                num += grid[0].length - pos;
            }
        }
        return num;
    }
}

正序遍历的解法，代码来源于1351-LeetCode官方解法：

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int num = 0, m = (int) grid[0].size(), pos = (int) grid[0].size() - 1;
        for (auto x : grid) {
            int i;
            for (i = pos; i >= 0; --i) {
                if (x[i] >= 0) {
                    if (i + 1 < m) {
                        pos = i + 1;
                        num += m - pos;
                    }
                    break;
                }
            }
            if (i == -1) {
                num += m;
                pos = -1;
            }
        }
        return num;
    }
};

• 时间复杂度：\(O(n + m)\)，其中 n 是行数， m 是列数，外层循环遍历了每一行，时间复杂度为 \(O(n)\) ，而内层循环最多只需要移动 m 次位置即可，所以总的时间复杂度为 \(O(m + n)\)。

• 空间复杂度：\(O(1)\)，只使用了常数个变量。

每题一图