LeetCode题解之统计有序矩阵中的负数

统计有序矩阵中的负数

题目描述

给你一个 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

示例 3:

输入：grid = [[1,-1],[-1,-1]]
输出：3

示例 4:

输入：grid = [[-1]]
输出：1

提示：

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

解题思路

方法一：暴力法

直接暴力迭代求解。

复杂度分析

• 时间复杂度：O(n*m)。
• 空间复杂度：O(1)。

代码实现

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

方法二：二分法

根据题意可知，矩阵中的元素无论是按行还是按列，都以非递增顺序排列，因此可以使用二分法来找到每一行中第一个负数所在的位置，那么就可以知道这一行中负数的个数了。依次计算每一行中负数的个数即可得到答案。

复杂度分析

• 时间复杂度：O(nlogm)。
• 空间复杂度：O(1)。

代码实现

class Solution {
    public int countNegatives(int[][] grid) {
        int res = 0, right = grid[0].length, left = 0;
        for(int i = 0; i < grid.length; i ++) {
            left=0;
            while(left < right) {
                int middle= ((left + right) >> 1);
                if(grid[i][middle] >= 0) {
                    left= middle + 1;
                } else {
                    right = middle;
                }
            }
            res += (grid[0].length - left);
        }
        return res;
    }
}