# 1351. Count Negative Numbers in a Sorted Matrix
###### tags: `Python`,`Leetcode`
https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/
### 暴力法

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] < 0 :
                    count += 1
                else :
                    continue
        return count

### 稍微溫柔仍然暴力法

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0]) # 列長、行長
        r, c, count = 0, n - 1, 0 # r(row)列 index 、 c(column)行 index、計數
        while r < m and c >= 0: # r index 不超過列長 column 從下看到上
            if grid[r][c] < 0: # 如果 < 0，則代表 r ~ m 是我們要的
                count += m - r # 計算數量
                c -= 1 # 算完換行數量
            else:
                r += 1 # 如果 > 0 ，該 r index 就要慢慢往右直到變負的
        return count

### Hint 希望我做但我想不到法
結果只是一列一列 Binary Search 😅 無聊

class Solution(object):
    def countNegatives(self, grid):
        def bin(row):
            start, end = 0, len(row)
            while start<end:
                mid = (start + end)// 2
                if row[mid]<0:
                    end = mid
                else:
                    start = mid+1
            return len(row)- start
        
        count = 0
        for row in grid:
            count += bin(row)
        return(count)