一个二维矩阵，从左到右，总上到下数字不增，求矩阵中负数有多少，水题
思路一：设个游标，记录当前行非负数有几个
1 #1351
2 #Runtime: 95 ms (Beats 68.82%)
3 #Memory: 14.5 MB (Beats 73.12%)
4
5 class Solution(object):
6 def countNegatives(self, grid):
7 """
8 :type grid: List[List[int]]
9 :rtype: int
10 """
11 pos = len(grid[0])
12 ans = 0
13 for i in range(len(grid)):
14 for j in range(pos):
15 if grid[i][j] < 0:
16 pos = j
17 break
18 ans += len(grid[0]) - pos
19 return ans
思路二：每行二分求位置（复杂度更低，但这题数据估计很水，所以反而慢）
1 #1351
2 #Runtime: 102 ms (Beats 25.81%)
3 #Memory: 14.5 MB (Beats 40.86%)
4
5 class Solution(object):
6 def countNegatives(self, grid):
7 """
8 :type grid: List[List[int]]
9 :rtype: int
10 """
11 def b_search(i):
12 l = 0
13 r = len(grid[i])
14 while l < r:
15 mid = (l + r) // 2
16 if grid[i][mid] >= 0:
17 l = mid + 1
18 else:
19 r = mid
20 return l
21
22 ans = 0
23 for i in range(len(grid)):
24 ans += len(grid[0]) - b_search(i)
25 return ans