统计有序矩阵中的负数
难度:
标签:
题目描述
代码结果
运行时间: 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)
代码细节讲解
🦆
题解中提到`如果当前行的最小元素是非负的,跳过当前行`,但是为什么只检查行的最后一个元素而不是整行元素?
▷🦆
在算法中,当遇到第一个负数时直接计算剩余负数数量并跳过,这种方法是否在所有情况下都正确?
▷🦆
算法实现中使用了`min(grid[i])`来判断行中是否有负数,这是否增加了不必要的计算,因为非严格递减的性质是否意味着只需要检查行的最后一个元素?
▷🦆
该解法在最坏情况下每行都要完全遍历,是否有更高效的遍历方法考虑到矩阵的非严格递减排序?
▷