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
}