1351统计矩阵中的负数个数

title: 1351.统计有序矩阵中的负数

?? 题目描述

题目链接：统计矩阵中的负数

?? 解题思路

每层遍历的做法为o(n*m)，将每一层的搜索加快，采用二分查找，可以套用找边界问题，找<0的左边界

int countNegatives(vector>& grid) {
    int len = grid.size() - 1;
    int left, right, mid;
    int res = 0;
    
    for (int i = 0; i <= len; i++) {
        left = 0, right = grid[i].size() - 1;
        
        while (left < right) {
            mid = left + ((right - left) >> 1);
            
            if (grid[i][mid] >= 0) left = mid + 1;//缩小左边边界。依据题意来
            else right = mid;//缩小右边边界
        }
        
        res += grid[i][left] < 0 ? grid[i].size() - left : 0;
    }
    return res;
} 

?? 复杂度分析

• 空间复杂度：o(1)
• 时间复杂度：o(m*logn)