题目大意：
统计有序矩阵中的负数
给你一个 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
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1351
解题思路分析：
我们之前的文章讲过，看到这种横竖都排列好的矩阵问题，应该下意识想到从左下角开始遍历数组。也就是从矩阵最后一行的首列开始遍历，如果当前数字不是负数，向右移动一格，反之如果当前数是负数，说明该数字之后都是负数，累加当前列到尾列的个数到返回结果。然后向上移动一格，继续重复上述步骤，直到当前位置超出矩阵范围为止。
实现代码：
public int countNegatives(int[][] grid) {
// 初始化当前行为最后一行
int row = grid.length-1;
// 初始化当前列为第一列
int col = 0;
// 返回结果
int res=0;
// 当位置没有超出矩阵范围时循环
while(row>=0&&col<grid[0].length){
// 如果当前数字小于0
if(grid[row][col]<0){
// 累加当前列到尾列的数量
res+=grid[0].length-col;
// 同时向上移动一格
row--;
}else{
// 反之向有移动一格
col++;
}
}
return res;
} 本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Count Negative Numbers in a Sorted Matrix.
Memory Usage: 41.8 MB, less than 100.00% of Java online submissions for Count Negative Numbers in a Sorted Matrix.
进阶：另外本题可以使用二分查找来做进一步的优化，我们在当前列到尾列的范围内使用二分查找找到第一个负数的位置，这样可以优化横向移动的遍历时间。
二分查找实现代码：
public int countNegatives(int[][] grid) {
int row = grid.length-1;
int col = 0;
int res=0;
while(row>=0&&col<grid[0].length){
int l=col,r=grid[0].length-1;
while(l<=r){
int mid = (l+r)/2;
if(grid[row][mid]<0){
r=mid-1;
}else{
l=mid+1;
}
}
if(l<grid[0].length){
res+=grid[0].length-l;
}
row--;
}
return res;
} 本解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Count Negative Numbers in a Sorted Matrix.
Memory Usage: 41.6 MB, less than 100.00% of Java online submissions for Count Negative Numbers in a Sorted Matrix.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1351-count-negative-numbers-in-a-sorted-matrix-解题思路分析/