526互联

1351. 统计有序矩阵中的负数(leetcode)

发布时间 2023-04-26 22:34:46作者: 风乐

https://leetcode.cn/problems/count-negative-numbers-in-a-sorted-matrix/

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

1.二分法:把每一行进行一遍二分,找到正数与负数的边界,且此时grid[i][mid]也为负数,即边界下标的对应值是负数的左半边界
那么一行中的个数即为size()-l

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int cnt=0;
        for(int i=0;i<grid.size();i++)
        {
            int l=0,r=grid[i].size();
            int mid;
            while(l<r)
            {
                int mid=l+r>>1;
                if(grid[i][mid]>=0)l=mid+1,flag=mid;
                else r=mid;
            }
            cnt+=grid[i].size()-l;
        }
        return cnt;
    }
};

2.双指针,利用矩阵从左到右递减,从上到下递减的规律,可以知道i,j的变化都具有单调性,且j不会回溯为n,故可用双指针

由于是while(j>=0)j--,因此最后j为-1,那么答案-j后需要

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int cnt=0;
        int n=grid.size(),m=grid[0].size();
        for(int i=0,j=m-1;i<n;i++)
        {
            while(j>=0 && grid[i][j]<0)j--;
            cnt+=m-j-1;
        }
        return cnt;
    }
};