统计有序矩阵中的负数Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你一个 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) 的解决方案吗？
# 思路
从右上角遍历O(m+n)
# 解法
class Solution {
// 从右上角遍历O(m+n)
public int countNegatives(int[][] grid) {
int res = 0;
int row = 0, col = grid[0].length - 1;
// 从最右上角开始
while (row < grid.length && col >= 0) {
if (grid[row][col] < 0) {
res += grid.length - row;
// 向左移动
col--;
} else {
// 向下移动
row++;
}
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 总结
- 分析出几种情况，然后分别对各个情况实现
