1351. Count Negative Numbers in a Sorted Matrix

Easy

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.

Example 2:

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

Constraints:

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 100

• -100 <= grid[i][j] <= 100

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

解題

解法一：從最後一個元素開始一個個查找，若遇到非負元素，中斷該列查找。

func countNegatives(grid [][]int) int {
    res := 0

    for i := len(grid) - 1; i >= 0; i-- {
        for j := len(grid[0]) - 1; j >= 0; j-- {
            if grid[i][j] < 0 {
                res++
            } else {
                break
            }
        }
    }

    return res
}

解法二：Binary Search

func countNegatives(grid [][]int) int {
    res := 0

    for _, row := range grid {
        index := binarySearch(row)
        res += len(row) - index
    }

    return res
}

func binarySearch(row []int) int {
    left := 0
    right := len(row) - 1

    for left <= right {

        mid := (left + right) / 2

        if row[mid] >= 0 {
            left = mid + 1 
        } else {
            right = mid - 1
        }
    }

    //如果沒有非負的整數，會回傳 len(row)
    return left
}