1351. Count Negative Numbers in a Sorted Matrix

解題思路

先以單一個 row 來看，要怎麼找有幾個負數？

根據題目說明的特性，只要找到從哪裡開始都是負數的位置就好。那可以用 binary search。

譬如：[4,3,2,-1]，最後 left 會停在 -1 的位置，那就可以算有幾個負數。

另外，因為下面的 row 肯定負數/正數的邊界只會越靠左，所以可以先存這邊以加快速度。

程式碼

class Solution {
public:
    int helper(vector<vector<int>>& grid, int& right, int row)
    {
        int left = 0;
        while(left <= right)
        {
            int mid = (left + right) / 2;
            if(grid[row][mid] >= 0)
                left++;
            else
                right--;
        }
        right = min(right, left);
        return grid[row].size() - left;
    }
    int countNegatives(vector<vector<int>>& grid) {
        int ans = 0, right = grid[0].size() - 1;
        for(int i=0; i<grid.size(); i++)
        {
            ans += helper(grid, right, i);
        }
        return ans;
    }
};