一個二維矩陣，從左到右，總上到下數(shù)字不增，求矩陣中負(fù)數(shù)有多少，水題
思路一：設(shè)個游標(biāo)，記錄當(dāng)前行非負(fù)數(shù)有幾個
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
思路二：每行二分求位置（復(fù)雜度更低，但這題數(shù)據(jù)估計很水，所以反而慢）
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