Last Updated on 2023-12-14 by Clay
題目
You are given a 0-indexed m x n
binary matrix grid
.
A 0-indexed m x n
difference matrix diff
is created with the following procedure:
- Let the number of ones in the
ith
row beonesRowi
. - Let the number of ones in the
jth
column beonesColj
. - Let the number of zeros in the
ith
row bezerosRowi
. - Let the number of zeros in the
jth
column bezerosColj
. diff[i][j] = onesRowi + onesColj - zerosRowi - zerosColj
Return the difference matrix diff
.
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 <= 105
1 <= m * n <= 105
grid[i][j]
is either0
or1
.
我們需要返回一組新的 m x n 的陣列,並且其中每個元素都是由原本輸入的 grid
中的行中的 1 數量減去 0 的數量、以及列中的 1 數量減去 0 的數量兩者相加而得到。
解題思路
以下作法應該不是最優解,但我認為十分直覺。
將各行列的 1 和 0 各自加總起來,使用 onesRow
, onesCol
, zerosRow
, zerosCol
四個陣列儲存起來。比方說 onesRow
的第 i 個元素,代表著第 row i
的所有 1 加總之值... 依此類推。
這樣做的好處是,當我們開始重新計算新的 m x n 陣列的最終值時,我們只需要取 onesRow[i] + onesCol[j] - zerosRow[i] - zerosCol[j] 就可以得到新陣列的 (i, j) 之值。
C++ 範例程式碼
class Solution {
public:
vector<vector<int>> onesMinusZeros(vector<vector<int>>& grid) {
// Init
int rowSize = grid.size();
int colSize = grid[0].size();
vector<int> onesRow(rowSize, 0);
vector<int> onesCol(colSize, 0);
vector<int> zerosRow(rowSize, 0);
vector<int> zerosCol(colSize, 0);
// Count the accumulates of columns and rows
for (int i=0; i<rowSize; ++i) {
for (int j=0; j<colSize; ++j) {
if (grid[i][j] == 1) {
++onesRow[i];
++onesCol[j];
}
else {
++zerosRow[i];
++zerosCol[j];
}
}
}
// Fill the results
for (int i=0; i<rowSize; ++i) {
for (int j=0; j<colSize; ++j) {
int element = onesRow[i] + onesCol[j] - zerosRow[i] - zerosCol[j];
grid[i][j] = element;
}
}
return grid;
}
};
Python 範例程式碼
class Solution:
def onesMinusZeros(self, grid: List[List[int]]) -> List[List[int]]:
# Init
rowSize = len(grid)
colSize = len(grid[0])
onesRow = [0] * rowSize
onesCol = [0] * colSize
zerosRow = [0] * rowSize
zerosCol = [0] * colSize
# Count the accumulates of columns and rows
for i in range(rowSize):
for j in range(colSize):
if grid[i][j] == 1:
onesRow[i] += 1
onesCol[j] += 1
else:
zerosRow[i] += 1
zerosCol[j] += 1
# Fill the results
for i in range(rowSize):
for j in range(colSize):
grid[i][j] = onesRow[i] + onesCol[j] - zerosRow[i] - zerosCol[j]
return grid