leetcode
leetcode 1251 ~ 1300
统计有序矩阵中的负数

统计有序矩阵中的负数

难度:

标签:

题目描述

代码结果

运行时间: 19 ms, 内存: 17.0 MB


/*
 * 题目思路:
 * 给定一个m*n的矩阵grid,矩阵中的元素无论是按行还是按列,都以非严格递减顺序排列。
 * 我们需要统计并返回grid中负数的数目。
 * 可以使用Java Stream来简化代码。
 */

import java.util.Arrays;

public class Solution {
    public int countNegatives(int[][] grid) {
        return (int) Arrays.stream(grid)
                .flatMapToInt(Arrays::stream)
                .filter(x -> x < 0)
                .count();
    }
}

解释

方法:

这个题解使用了逐行扫描的方法来统计负数的数量。首先,它检查每一行的最小元素(即行的最后一个元素,因为行是非严格递减的),如果这个元素是非负的,那么这一行就不包含负数,可以直接跳过。如果这个元素是负数,那么它从当前行的开头开始扫描,直到找到第一个负数,然后通过'剩余列数'来增加负数的计数(因为后面的元素都是负数),然后跳出循环进入下一行。

时间复杂度:

O(m*n)

空间复杂度:

O(1)

代码细节讲解

🦆
题解中提到`如果当前行的最小元素是非负的,跳过当前行`,但是为什么只检查行的最后一个元素而不是整行元素?
在题解中,由于矩阵的每一行是非严格递减的,最后一个元素是该行中的最小元素。因此,只需检查每行的最后一个元素是否为负数即可判断该行是否含有负数。如果最后一个元素是非负的,那么整行都是非负的,无需进一步检查。
🦆
在算法中,当遇到第一个负数时直接计算剩余负数数量并跳过,这种方法是否在所有情况下都正确?
是的,这种方法在所有情况下都是正确的。因为每行是非严格递减的,一旦某个元素是负数,该元素右侧的所有元素也必定是负数。因此,可以直接通过 n - j(n是列数,j是第一个负数的索引)计算出该行剩余的负数数量。
🦆
算法实现中使用了`min(grid[i])`来判断行中是否有负数,这是否增加了不必要的计算,因为非严格递减的性质是否意味着只需要检查行的最后一个元素?
确实,使用`min(grid[i])`进行判断增加了不必要的计算。非严格递减的性质确实意味着只需要检查每行的最后一个元素就足够了。因此,可以改进算法,直接检查每行的最后一个元素,而不是使用`min`函数,以提高算法的效率。
🦆
该解法在最坏情况下每行都要完全遍历,是否有更高效的遍历方法考虑到矩阵的非严格递减排序?
可以使用更高效的方法,如二分查找,来找到每行中第一个负数的位置。由于每行都是非严格递减排序的,可以利用这一点在每行应用二分查找,以更快地找到转折点(从非负到负数的位置)。这样可以减少不必要的遍历,尤其是在负数出现位置较晚的情况下,大大提高效率。

相关问题