Count Negative Numbers in a Sorted Matrix

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

Example 1:

Input: grid = [
[4,3,2,-1],
[3,2,1,-1],
[1,1,-1,-2],
[-1,-1,-2,-3]
]
Output: 8
Explanation: There are 8 negatives number in the matrix.

Follow up: Could you find an O(n + m) solution?

My Solutions:

根据题意，每一行的数字递减，每一列的数字也是递减的。所以可以从grid的左下角开始，往右或者往上移动。也可以从右上角开始，往左或者往下移动

class Solution {
    public int countNegatives(int[][] grid) {
        int m = grid.length, n = grid[0].length, count = 0;

        // 从grid的左下角开始
        int r = m - 1, c = 0;
        while (r >= 0 && c < n) { 
            if (grid[r][c] < 0) {  // 现在格子的这一行肯定都是negative number
                r--; // 把行数往上移动一位
                count += n - c; // 列数-c所在的位置
            } else { // 向右移动
                c++;
            }
        }

        // // 或者从grid的右上角开始
        // int r = 0, c = n - 1;
        // while (r < m && c >= 0) { 
        //     if (grid[r][c] < 0) {  // 现在格子的下面一列肯定都是negative number
        //         c--; // 把列数往左移动一位
        //         count += m - r;
        //     } else {
        //         r++;
        //     }
        // }

        return count;
    }
}

这个题目也可以变形成每一行的数字递增，每一列递增。

Give a horizontally sorted and vertically sorted n * m matrix, find the number of negative number.

Example 1:

Input:[    
[-5,-3,-1,0,1],    
[-2,-1,0,0,1],    
[0,11,12,12,14]
]
Output: 5
Explanation: There are only 5 negative number.

Example 2:

Input:[    
[-50,-30,-10,-5],    
[-30,-20,-5,-1],    
[-10,-5,-1,0]
]
Output: 11
Explanation: There are only 11 negative number.

My Solutions:

类似的从右上角开始，往左和往下移动

public int countNumber(int[][] nums) {
    // Write your code here
    int count = 0, m = nums.length, n = nums[0].length;
    int r = 0, c = n - 1;
    while (r < m && c >= 0) {
        if (nums[r][c] < 0) { // 现在格子的一行都是负数
            count += c + 1;
            r++; // 移动到下一行
        } else {
            c--; // 现在的格子是正数，移动到左边的一列
        }
    }
    return count;
}