矩陣0與1的差值 Leetcode 2484 Diff Between 1s and 0s in Row and Col

Joshua Sortino on Unsplash

題目敘述

題目會給定我們一個二元矩陣grid，要求我們計算這個矩陣的Difference值，並且以矩陣的形式返回答案。

對於grid[i][j] 的Difference值定義

- 同一個row i裡面 0的數目 + 同一個column j裡面 0的數目

(類似小時候玩電動，炸彈超人的十字線炸彈爆炸的走法)

下方測試範例有詳細的解說與計算過程

詳細的題目可在這裡看到

測試範例

Example 1:

Input: grid = [[0,1,1],[1,0,1],[0,0,1]]
Output: [[0,0,4],[0,0,4],[-2,-2,2]]
Explanation:
- diff[0][0] = onesRow0 + onesCol0 - zerosRow0 - zerosCol0 = 2 + 1 - 1 - 2 = 0 
- diff[0][1] = onesRow0 + onesCol1 - zerosRow0 - zerosCol1 = 2 + 1 - 1 - 2 = 0 
- diff[0][2] = onesRow0 + onesCol2 - zerosRow0 - zerosCol2 = 2 + 3 - 1 - 0 = 4 
- diff[1][0] = onesRow1 + onesCol0 - zerosRow1 - zerosCol0 = 2 + 1 - 1 - 2 = 0 
- diff[1][1] = onesRow1 + onesCol1 - zerosRow1 - zerosCol1 = 2 + 1 - 1 - 2 = 0 
- diff[1][2] = onesRow1 + onesCol2 - zerosRow1 - zerosCol2 = 2 + 3 - 1 - 0 = 4 
- diff[2][0] = onesRow2 + onesCol0 - zerosRow2 - zerosCol0 = 1 + 1 - 2 - 2 = -2
- diff[2][1] = onesRow2 + onesCol1 - zerosRow2 - zerosCol1 = 1 + 1 - 2 - 2 = -2
- diff[2][2] = onesRow2 + onesCol2 - zerosRow2 - zerosCol2 = 1 + 3 - 2 - 0 = 2

Example 2:

Input: grid = [[1,1,1],[1,1,1]]
Output: [[5,5,5],[5,5,5]]
Explanation:
- diff[0][0] = onesRow0 + onesCol0 - zerosRow0 - zerosCol0 = 3 + 2 - 0 - 0 = 5
- diff[0][1] = onesRow0 + onesCol1 - zerosRow0 - zerosCol1 = 3 + 2 - 0 - 0 = 5
- diff[0][2] = onesRow0 + onesCol2 - zerosRow0 - zerosCol2 = 3 + 2 - 0 - 0 = 5
- diff[1][0] = onesRow1 + onesCol0 - zerosRow1 - zerosCol0 = 3 + 2 - 0 - 0 = 5
- diff[1][1] = onesRow1 + onesCol1 - zerosRow1 - zerosCol1 = 3 + 2 - 0 - 0 = 5
- diff[1][2] = onesRow1 + onesCol2 - zerosRow1 - zerosCol2 = 3 + 2 - 0 - 0 = 5
 

約束條件

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10^5
• 1 <= m * n <= 10^5
• grid[i][j] is either 0 or 1.

演算法

除了第一直覺的暴力三次方搜索以外，還有一個更為精簡的二次方演算法。

題目已經講了輸入是二元矩陣。陣列元素要嘛是1，要嘛是0。

所以，當我們知道這條row的1的總數目，其實，相對應0的總數目也知道了。

當下這條row的0的總數目= 矩陣的寬 - 當下這條row的1的總數目。

同理類推，當我們知道這條column的1的總數目，其實，相對應0的總數目也知道了。

當下這條column的0的總數目= 矩陣的高 - 當下這條column的1的總數目。

因此，建立並且維護兩個字典，

第一個字典負責記錄每條row 1的總數目。

第二個字典負責記錄每條column 1的總數目。

用一個2D二維的線性掃描，更新字典，最後依照剛剛推導出的關係式，根據題目定義計算Diff值即可。

程式碼

class Solution:
 　def onesMinusZeros(self, grid: List[List[int]]) -> List[List[int]]:
 　　
 　　# key: row index
 　　# value: 1s count on corresponding row
 　　rowOnes = defaultdict(int)
 
 　　# key: column index
 　　# value: 1s count on corresponding column
 　　colOnes = defaultdict(int)
 
 　　# Height as well as Width of input matrix
 　　h, w = len(grid), len(grid[0])
 　　
 　　# Update 1s count with respect to specific column and row
 　　for y in range(h):
 　　　for x in range(w):
 
 　　　　if grid[y][x] == 1:
 　　　　　rowOnes[y] += 1
 　　　　　colOnes[x] += 1
 
 
 　　# Just follow the definition in description
 　　# Diff = 1s Count - 0s Count　　
 　　for y in range(h):
 　　　for x in range(w):
 　　　　
 　　　　# In-place update
 　　　　grid[y][x] = rowOnes[y] + colOnes[x] - (w-rowOnes[y]) - (h-colOnes[x])
 
 　　return grid​

複雜度分析

時間複雜度:

O( mn ) 兩次二維掃描，成本皆為O(mn) = O(矩陣的寬 * 矩陣的高)。

空間複雜度:

O( m+n ) 使用到的是兩個字典，分別占用寬與高的大小。

第一個字典O(m) 紀錄每條row 1的總數目

第二個字典O(n) 紀錄每條column 1的總數目

關鍵知識點:

主要的考點在於HashMap 雜湊映射表，在python中就是dictionary字典的應用。

題目已經講了輸入是二元矩陣。陣列元素要嘛是1，要嘛是0。

所以，當我們知道這條row的1的總數目，其實，相對應0的總數目也知道了。

當下這條row的0的總數目= 矩陣的寬 - 當下這條row的1的總數目。

同理類推，當我們知道這條column的1的總數目，其實，相對應0的總數目也知道了。

當下這條column的0的總數目= 矩陣的高 - 當下這條column的1的總數目。

Reference:

[1] Python O(mn) by hashMap (dictionary) [w/ Comment] - Difference Between Ones and Zeros in Row and Column - LeetCode