题目描述

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

Given a m * 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.
Example 2:

Input: grid = [[3,2],[1,0]]
Output: 0
Example 3:

Input: grid = [[1,-1],[-1,-1]]
Output: 3
Example 4:

Input: grid = [[-1]]
Output: 1
 

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100

博主第一次提交的代码

这次写的我觉得还行，但在性能上没有使用二分法

public int countNegatives(int[][] grid) {
        int result = 0;
        int rowMax = grid.length;
        int colMax = grid[0].length;
        for(int i = 0; i < rowMax; i++){
            int[] col = grid[i];
            for(int j = 0; j < colMax; j++){
                if(col[j] < 0){
                    int tmp = (rowMax -i ) * ( colMax-j);
                    result += tmp ;
                    colMax = j;
                }
            }
        }
        return result;
    }

他人优秀简洁的代码

解法一

https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/discuss/510247/Java-O(M-%2B-N)-Solution

从右上角开始遍历
public int countNegatives(int[][] grid) {
        int res = 0;
        int m = grid.length;
        int n = grid[0].length;
        int i = 0;
        int j = n - 1;
        while (i < m && j >= 0) {
            if (grid[i][j] < 0) {
                res += m - i;
                j--;
            } else {
                i++;
            }
        }
        return res;
    }

解法二

这个优秀，还用了二分法找小于0的数
https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/discuss/510303/Java-solution-%3A-n(log-n)

public int countNegatives(int[][] grid) {
    int res = 0;
    for(int[] row : grid){
        res += bs(row);
    }
    return res;
}

int bs(int[] row){
    int l = 0, r = row.length;
    while(l < r){
        int m = l + (r - l)/2;
        if(row[m] < 0)
            r = m;
        else
            l = m + 1;
    }
    return row.length - l;
}

解法三

https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/discuss/512165/Java-binary-search-beats-100-explained

This problem can be solved with a binary search.

For every row do the binary search to find exact position of the fist negative element, after that all elements are negative. Optimization here - for every next row the right limit for the binary search can be the index of the first negative from the previous row. This is due to fact that cols are also sorted so for the same column for every negative element the element below can be only negative. Thus we can explude it from the binary search on the next step.

Also taking care of the edge cases helps - if first element is < 0 then all elements in a row are negative, if last one is non-negative then all elements are non-negative.

O(rows x lg(cols)) time - need to do lg(cols) binary search for each of rows row, O(1) space - no extrace space other than few variables.

    public int countNegatives(int[][] grid) {
        int rows = grid.length, cols = grid[0].length; 
        int res = 0, lastNeg = cols - 1;
        for (int row = 0; row < rows; row++) {
            //check edge cases - if first element is < 0 - all elements in row are negative
            if (grid[row][0] < 0) {
                res+=cols;
                continue;
            }
            //if last element is positive - it means there are no negative numbers in a row
            if (grid[row][cols - 1] > 0)
                continue;
            //there is a mix of negative and positive ones, need to find the border. starting
            //binary search
            int l = 0, r = lastNeg;
            while (l <= r) {
                int m = l + (r - l)/2;
                if (grid[row][m] < 0) {
                    r = m - 1;
                } else
                    l = m + 1;
            }
            //l points to the first negative element, which means cols - l is a number of
            //such elements
            res += (cols - l); lastNeg = l;
        }
        return res;
    }s