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.lengthn == grid[i].length1 <= 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
}