LeetCode: 2482-Difference Between Ones and Zeros in Row and Column 解題紀錄

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 be onesRowi.
• Let the number of ones in the jth column be onesColj.
• Let the number of zeros in the ith row be zerosRowi.
• Let the number of zeros in the jth column be zerosColj.
• 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] = onesRow₀ + onesCol₀ - zerosRow₀ - zerosCol₀ = 3 + 2 - 0 - 0 = 5 - diff[0][1] = onesRow₀ + onesCol₁ - zerosRow₀ - zerosCol₁ = 3 + 2 - 0 - 0 = 5 - diff[0][2] = onesRow₀ + onesCol₂ - zerosRow₀ - zerosCol₂ = 3 + 2 - 0 - 0 = 5 - diff[1][0] = onesRow₁ + onesCol₀ - zerosRow₁ - zerosCol₀ = 3 + 2 - 0 - 0 = 5 - diff[1][1] = onesRow₁ + onesCol₁ - zerosRow₁ - zerosCol₁ = 3 + 2 - 0 - 0 = 5 - diff[1][2] = onesRow₁ + onesCol₂ - zerosRow₁ - zerosCol₂ = 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 either 0 or 1.

我們需要返回一組新的 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

---

References

• 2482. Difference Between Ones and Zeros in Row and Column

---

Read More

• LeetCode 解題紀錄目錄