【Leetcode完整解答筆記】1351. Count Negative Numbers in a Sorted Matrix

現在有一個 m x n ,沒有經過排序的陣列,找出負數的整數總數。

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

Example 3:

Input: grid = [[1,-1],[-1,-1]]
Output: 3

Example 4:

Input: grid = [[-1]]
Output: 1

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?

解題說明:

陣列裡的大小都是照著由小到大的排序,以 grid[r][c] 說明。如果 grid[3][0] < 0,那 grid[3][1] 到 grid[3][2] 都一定 <0。

相加到 cnt 後把 r 減一,這時就可以接著往 grid[2][0]判斷,如果 grid[2][0] > 0 就增加 c,往 grid[2][1] 找,以此類推。

Python 解答:

class Solution:
     def countNegatives(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        r, c, cnt = m - 1, 0, 0
        while r >= 0 and c < n:
            if grid[r][c] < 0:
                cnt += n - c
                r -= 1
            else:
                c += 1
        return cnt

從題目中我們可以得知,題目提供的陣列一定是二維陣列。

接下來我們仔細看程式的細節。

while r >= 0 and c < n:
    if grid[r][c] < 0:
        cnt += n - c
        r -= 1
    else:
        c += 1

以以下的輸入為例。

[[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]

當 grid 的長度 >=0 並且 grid[0] 的長度 > 0,

Round 1:

r=3, grid[r][c] = grid[3][0]=-1 (<0)
cnt = n – c=4-0=4

Round 2:

r=2, grid[r][c] = grid[2][0]=1 (>0)
進入 else , 導致,c+=1,這時 c=1

Round 3:

r=2, grid[r][c] = grid[2][1]=1 (>0)
進入 else , 導致,c+=1,這時 c=2

Round 4:

r=2, grid[r][c] = grid[2][2]=-1 (<0)
cnt += n – c=4+4-2=6
r -= 1

Round 5:

r=1, grid[r][c] = grid[1][2]=1 (>0)
進入 else , 導致,c+=1,這時 c=3

Round 6:

r=1, grid[r][c] = grid[1][3]=-1 (<0)
cnt += n – c=6+4-3=7
r -= 1

Round 7:

r=0, grid[r][c] = grid[0][3]=-1 (<0)
cnt += n – c=7+4-3=8
r -= 1

分析:用 grid[0] 是因為 grid[1],grid[2] 等的長度都一樣,而且可能根據題目,可能出現 [[-1]] 的情況。

Leave a Comment

Your email address will not be published. Required fields are marked *