46 Count Negative Numbers in a Sorted Matrix
46 Count Negative Numbers in a Sorted Matrix
devi
发布于 2021-08-18 16:18:52
发布于 2021-08-18 16:18:52
代码可运行
运行总次数：0
代码可运行
题目
Given a m * n matrix grid which is sorted in non-increasing order both row-wise and column-wise.
Return the number of negative numbers in grid.
Example 1:
Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] Output: 8 Explanation: There are 8 negatives number in the matrix.
Example 2:
Input: grid = [[3,2],[1,0]] Output: 0
Example 3:
Input: grid = [[1,-1],[-1,-1]] Output: 3
Example 4:
Input: grid = [[-1]] Output: 1
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100分析
题意：给定降序排列的二维矩阵，返回负数的个数。
显然，题目强调矩阵是降序排列的，因此应该存在特殊的解法，而不是“直接遍历矩阵判断数字是否小于0就让count++”这么无脑。
不过，我们还是先写一个无脑的算法吧，毕竟，先解决问题，再考虑优化。
class Solution {
public int countNegatives(int[][] grid) {
int count=0;
for(int i=0;i<grid.length;++i)
for(int j=0;j<grid[i].length;++j)
if(grid[i][j]<0)
count++;
return count;
}
}
O(n²)时间复杂度。
也很容易想到，如果当前数字小于零，那么后面的都小于零，没必要遍历了，因此可以跳过后面的遍历。
去看看了评论区的答案，有O（m+n）的方法。
解答
class Solution {
public int countNegatives(int[][] grid) {
// m行n列，r表示当前行，c表示当前列
// 初始遍历位置为最后一行的第一列，从“左下”往“右上”遍历
int m = grid.length, n = grid[0].length, r = m - 1, c = 0, res = 0;
// 遍历结束条件
while (r >= 0 && c < n) {
// 如果当前数字小于零
if (grid[r][c] < 0) {
// 就将后续的长度加到结果上
res += n - c;
// 并跳过当前行
--r;
}else {
// 否则就继续查看下一个(列)数字
++c;
}
}
return res;
}
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/03/11 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
