统计有序矩阵中的负数

题目链接

统计有序矩阵中的负数

题目描述

注意点

• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100
• 矩阵中的元素无论是按行还是按列，都以非严格递减顺序排列

解答思路

• 第一种思路是遍历每一行，再对每行进行二分查找找到每一行第一个负数的位置，求得该行负数的数量，将每一行的结果相加即可
• 因为矩阵中的元素无论是按行还是按列，都以非严格递减顺序排列。所以在找到某一行最后一个正数的位置preCol后（此时该行的负数数量为n - preCol - 1），且下一行preCol之后的元素肯定都是负数（按行递减），所以下一行只需要从preCol开始往前遍历，继续找到下一行最后一个整数的列即可，以此类推，找到每一行的负数数量相加即可

代码

class Solution {public int countNegatives(int[][] grid) {int res = 0;int m = grid.length;int n = grid[0].length;// 上一行最后一个正数的列int preCol = n - 1;for (int i = 0; i < m; i++) {while (preCol >= 0 && grid[i][preCol] < 0) {preCol--;}res += n - preCol - 1;}return res;}
}

关键点

• 二分查找的思想
• 利用好矩阵中的元素无论是按行还是按列，都以非严格递减顺序排列的规律