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

更新於 發佈於 閱讀時間約 8 分鐘

題目敘述

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

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

= 同一個row i裡面 1的數目 + 同一個column j裡面 1的數目

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

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

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


詳細的題目可在這裡看到


測試範例

Example 1:

raw-image
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:

raw-image
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

avatar-img
91會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
題目敘述 題目會給我們兩張資料表,第一張是Sales,第二張是Product。 第一張是Sales表格,裡面分別有sale_id、 product_id、year、quantity、price等欄位。其中(sale_id、 product_id)做為複合主鍵Primary key
題目敘述 題目會給定一個整數陣列nums,要求我們找出最大的兩個整數a, b,返回(a-1) * (b-1)的乘積。 詳細的題目可在這裡看到 測試範例 Example 1: Input: nums = [3,4,5,2] Output: 12
題目敘述 題目會給我們一個字串,要求我們連三碼相同的數字,最大值是多少? 例如 給定輸入="1111222555333",最大值是555 如果無解,則返回空字串"" 英文版的題目敘述在這裡
題目敘述 題目會給我們一張Activity資料表,裡面分別有user_id、 session_id、activity_date 、activity_type等欄位。 要求我們列出所有過去30天的活躍使用者。 活躍使用者的定義為2019-07-27包含這天,往前三十天的區間內,至少有過一次活動紀錄
題目敘述 題目會給我們一張World資料表,裡面分別有name、 continent、area、population 、gdp等欄位,其中name 是主鍵Primary Key。 要求我們列出所有大型國家,大型國家的定義是 人口大於等於兩千五百萬人 或者 土地面積大於等於三百萬平方公里。 輸出順
題目敘述 題目會給我們一張Cinema資料表,裡面分別有id、movie、description, rating 等欄位,其中id 是主鍵Primary Key。 要求我們列出所有推薦人ID為奇數,而且不無聊的電影,印出時依照電影rating評分從高到低降序排列。 Table: Cinema
題目敘述 題目會給我們兩張資料表,第一張是Sales,第二張是Product。 第一張是Sales表格,裡面分別有sale_id、 product_id、year、quantity、price等欄位。其中(sale_id、 product_id)做為複合主鍵Primary key
題目敘述 題目會給定一個整數陣列nums,要求我們找出最大的兩個整數a, b,返回(a-1) * (b-1)的乘積。 詳細的題目可在這裡看到 測試範例 Example 1: Input: nums = [3,4,5,2] Output: 12
題目敘述 題目會給我們一個字串,要求我們連三碼相同的數字,最大值是多少? 例如 給定輸入="1111222555333",最大值是555 如果無解,則返回空字串"" 英文版的題目敘述在這裡
題目敘述 題目會給我們一張Activity資料表,裡面分別有user_id、 session_id、activity_date 、activity_type等欄位。 要求我們列出所有過去30天的活躍使用者。 活躍使用者的定義為2019-07-27包含這天,往前三十天的區間內,至少有過一次活動紀錄
題目敘述 題目會給我們一張World資料表,裡面分別有name、 continent、area、population 、gdp等欄位,其中name 是主鍵Primary Key。 要求我們列出所有大型國家,大型國家的定義是 人口大於等於兩千五百萬人 或者 土地面積大於等於三百萬平方公里。 輸出順
題目敘述 題目會給我們一張Cinema資料表,裡面分別有id、movie、description, rating 等欄位,其中id 是主鍵Primary Key。 要求我們列出所有推薦人ID為奇數,而且不無聊的電影,印出時依照電影rating評分從高到低降序排列。 Table: Cinema
你可能也想看
Google News 追蹤
Thumbnail
現代社會跟以前不同了,人人都有一支手機,只要打開就可以獲得各種資訊。過去想要辦卡或是開戶就要跑一趟銀行,然而如今科技快速發展之下,金融App無聲無息地進到你生活中。但同樣的,每一家銀行都有自己的App時,我們又該如何選擇呢?(本文係由國泰世華銀行邀約) 今天我會用不同角度帶大家看這款國泰世華CUB
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
這篇內容,將會講解什麼是陣列,以及與陣列相關的知識。包括陣列的簡介、陣列的資料限制、陣列的維度、一維陣列、二維陣列。
今天要來討論 1 + "1" 。 如果當兩個操作數都是數字時,+ 會執行數字相加。例如,1 + 1 結果是 2。 那如果是"1"+"1",就變成字符串相加變成11。 那我們今天要講的是1 + "1",答案是11,為甚麼呢? 這是一個類型強制轉換,今天當 + 遇到不一樣的類型時,JavaScrip
使用向量來處理問題有很多好處,其中一個好處,就是可以減少變數的數量。在這節中,會用一個簡單的例子來介紹,使用向量跟不使用向量,對變數的數量會有什麼樣的影響。
※ 何謂巢狀迴圈(NESTD LOOP): 指的是一個迴圈內包含另一個迴圈的結構。在程式設計中,這種結構常用於需要進行多層次迭代的場合,例如處理多維數組、逐行逐列處理表格資料等。 ※ 例子:九九乘法表 說明: 外層迴圈:for (let i = 1; i <= 9; i = i + 1) 這
Thumbnail
分享在網路上看到的陣列題目。通常 for...of 的 value 是陣列中的每個值,那如果我們在迭代中對陣列操作會發生什麼事? 題目來源:https://x.com/_jayphelps/status/1774640511158022335?s=20
Thumbnail
曾經對一個數學不好,但是喜歡玩電玩的親友小孩說,你現在討厭的正數,負數的代數計算,就是電玩裡頭的人物,可以左右上下移動,發射子彈,跳躍的基礎。 我舉微軟c語言寫遊戲的例子,(+,0)是向右,(-,0)是向左,(0,+)是向上,(0,-)是向下,(0,+)是向上,而跳躍旋轉則是三角函
Thumbnail
現代社會跟以前不同了,人人都有一支手機,只要打開就可以獲得各種資訊。過去想要辦卡或是開戶就要跑一趟銀行,然而如今科技快速發展之下,金融App無聲無息地進到你生活中。但同樣的,每一家銀行都有自己的App時,我們又該如何選擇呢?(本文係由國泰世華銀行邀約) 今天我會用不同角度帶大家看這款國泰世華CUB
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
這篇內容,將會講解什麼是陣列,以及與陣列相關的知識。包括陣列的簡介、陣列的資料限制、陣列的維度、一維陣列、二維陣列。
今天要來討論 1 + "1" 。 如果當兩個操作數都是數字時,+ 會執行數字相加。例如,1 + 1 結果是 2。 那如果是"1"+"1",就變成字符串相加變成11。 那我們今天要講的是1 + "1",答案是11,為甚麼呢? 這是一個類型強制轉換,今天當 + 遇到不一樣的類型時,JavaScrip
使用向量來處理問題有很多好處,其中一個好處,就是可以減少變數的數量。在這節中,會用一個簡單的例子來介紹,使用向量跟不使用向量,對變數的數量會有什麼樣的影響。
※ 何謂巢狀迴圈(NESTD LOOP): 指的是一個迴圈內包含另一個迴圈的結構。在程式設計中,這種結構常用於需要進行多層次迭代的場合,例如處理多維數組、逐行逐列處理表格資料等。 ※ 例子:九九乘法表 說明: 外層迴圈:for (let i = 1; i <= 9; i = i + 1) 這
Thumbnail
分享在網路上看到的陣列題目。通常 for...of 的 value 是陣列中的每個值,那如果我們在迭代中對陣列操作會發生什麼事? 題目來源:https://x.com/_jayphelps/status/1774640511158022335?s=20
Thumbnail
曾經對一個數學不好,但是喜歡玩電玩的親友小孩說,你現在討厭的正數,負數的代數計算,就是電玩裡頭的人物,可以左右上下移動,發射子彈,跳躍的基礎。 我舉微軟c語言寫遊戲的例子,(+,0)是向右,(-,0)是向左,(0,+)是向上,(0,-)是向下,(0,+)是向上,而跳躍旋轉則是三角函