统计有序矩阵中的负数

标题链接

统计有序矩阵中的负数
标题形貌

   

  留意点

• 1 <= m, n <= 100
  
• -100 <= grid[j] <= 100
  
• 矩阵中的元素无论是按行照旧按列，都以非严酷递减序次分列
  

解答思绪

• 第一种思绪是遍历每一行，再对每行举行二分查找找到每一行第一个负数的位置，求得该行负数的数量，将每一行的结果相加即可
  
• 由于矩阵中的元素无论是按行照旧按列，都以非严酷递减序次分列。以是在找到某一行末了一个正数的位置preCol后（此时该行的负数数量为n - preCol - 1），且下一行preCol之后的元素肯定都是负数（按行递减），以是下一行只必要从preCol开始往前遍历，继续找到下一行末了一个整数的列即可，以此类推，找到每一行的负数数量相加即可
  

代码

1. class Solution {
2.     public int countNegatives(int[][] grid) {
3.         int res = 0;
4.         int m = grid.length;
5.         int n = grid[0].length;
6.         // 上一行最后一个正数的列
7.         int preCol = n - 1;
8.         for (int i = 0; i < m; i++) {
9.             while (preCol >= 0 && grid[i][preCol] < 0) {
10.                 preCol--;
11.             }
12.             res += n - preCol - 1;
13.         }
14.         return res;
15.     }
16. }

复制代码

关键点

• 二分查找的头脑
  
• 利用好矩阵中的元素无论是按行照旧按列，都以非严酷递减序次分列的规律