1351.统计有序矩阵中的负数(高复杂度)

描述

(传送门)[https://leetcode-cn.com/problems/count-negative-numbers-in-a-sorted-matrix]
给你一个 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

解题思路

没啥好说的二分查找，对每一个二维数组中的每一行进行一个二分，一个for循环就够了，用来遍历每一行。这里注意越界的问题，因为是数组，在while中要加入一个边界的判断，内部两个if即可，大于等于0在一起。主要是最后的sum，注意减去的是left的值，因为left在最后一轮的判断中会移动到最先出现的那个负数那里，然而right判断是负数后会继续向左移动（因为此时不知道当前负数是不是最早的负数，同样left判断的是非零数，其无法识别是不是最后一个非零数，当判断是非零数向后移动一个且left大于right时此时找到了第一个负数），因此使用grid[i].length-left。全部循环完毕后得到最后的sum值。二分就是细节怪~~~~

代码

class Solution {
    public int countNegatives(int[][] grid) {
        		int sum=0;
        for (int i = 0; i < grid.length; i++) {

        	int left,mid,right;
        	left=0;
        	right=grid[i].length-1;
			mid=0;
			while(right>=left&&left<=grid[i].length&&right>=0) {
				mid=left+(right-left)/2;
				if(grid[i][mid]>=0) {
					left=mid+1;
				}
				else {
					right=mid-1;
				}
			}
			sum+=grid[i].length-left;
		}
        return sum;
    }
}