前往
大廳
主題

LeetCode - 1252. Cells with Odd Values in a Matrix 解題心得

Not In My Back Yard | 2021-04-09 00:00:07 | 巴幣 0 | 人氣 281

題目連結:


題目意譯:
現在有個 m × n 矩陣,其初始化為全部的值皆為 0。同時也有一個 2D 陣列 indices,其中 indices[i] = [ri, ci] 代表著一個索引值從 0 開始的位置,其為要執行一些增量操作的矩陣位置。

對於每個位置 indices[i],做以下兩件事:
將 ri 列的所有格子加 1。
將 ci 行的所有格子加 1。

給定 m 、 n 以及 indices,回傳經過所有 indices 的增量操作之後的矩陣,格子為奇數值的數量。

限制:
1 ≦ m 、 n ≦ 50
1 ≦ indices.length ≦ 100
0 ≦ ri < m
0 ≦ ci < n

進階: 你可以在 O(n + m + indices.length) 的時間複雜度以及 O(n + m) 的額外空間下解出這題嗎?



範例測資:
範例 1:
輸入: m = 2, n = 3, indices = [[0,1],[1,1]]
輸出: 6
解釋: 初始矩陣 = [[0,0,0],[0,0,0]]。
經過第一次增量後,其變為 [[1,2,1],[0,1,0]]。
最終矩陣為 [[1,3,1],[1,3,1]],其包含了 6 個奇數數字。

範例 2:
輸入: m = 2, n = 2, indices = [[1,1],[0,0]]
輸出: 0
解釋: 最終矩陣 = [[2,2],[2,2]]。最終矩陣內沒有任何奇數數字。


解題思維:
直接模擬所有增量操作,最後統計奇數的數量當然是可行的。不過,時間複雜度以及空間複雜度都可以壓到變成題目進階之要求:

因為每次增量只會 + 1,且所求只考慮最終矩陣內的奇數數字。因此,我們將每一列、每一行會被 + 1 幾次的「次數」儲存到兩個陣列 Ir 以及 Ic 內。

接著我們統計 Ir 、 Ic 中分別有多少「次數」為奇數,將其數量依序定作 Kr 和 Kc。然後我們先考慮只做增加列的情況:
對於增加次數為偶數的列,其列上的每個數字將會是偶數,所以不會列入所求數之中;相反地,增加次數為奇數的列,其列上每個數字都是奇數,所以都會納入所求中。且每列有著 n 個數字,因此只考慮列的情況下,奇數數字會有 Kr × n 個。

緊接著我們考慮進增加行的情況:
對於增加次數為偶數的行,因為奇數加偶數為奇數、偶數加偶數為奇數,因此奇偶性不會改變,所求數量也就不會跟著改變;相反地,增加次數為奇數的行,會使得該行上經過先前列的增量後為奇數的數字變為偶數、偶數的數字變為奇數。因此,所求數量會減少 X 個並增加 m - X 個奇數數字。

所以結合以上情況,最終矩陣的奇數數字將會是
(Kr × n) + (Kc × (m - 2Kr))
或者是將上述情況的行、列之角色互換,會得到
(Kr × (n - 2Kc)) + (Kc × m)
兩者皆等價於
Kr × n + Kc × m - 2KrKc




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作