題目描述

題目鏈接：1252. 奇數值單元格的數目

給你一個 m x n 的矩陣，最開始的時候，每個單元格中的值都是 0。

另有一個二維索引數組?indices，indices[i] = [ri, ci] 指向矩陣中的某個位置，其中 ri 和 ci 分別表示指定的行和列（從 0 開始編號）。

對 indices[i] 所指向的每個位置，應同時執行下述增量操作：

• ri 行上的所有單元格，加 1 。
• ci 列上的所有單元格，加 1 。 給你 m、n 和 indices 。請你在執行完所有?indices?指定的增量操作后，返回矩陣中 奇數值單元格 的數目。

進階： 你可以設計一個時間復雜度為?O(n + m + indices.length)?且僅用?O(n + m)?額外空間的算法來解決此問題嗎？

提示:

1 <= m, n <= 50

1 <= indices.length <= 100

0 <= ri?< m

0 <= ci?< n

示例 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]]，里面沒有奇數。

整理題意

題目給定一個 m x n 的矩陣，矩陣中每個元素最開始都為 0，然后給定一個二維數組?indices，數組中每個元素包含兩個值 indices[i][0] 和 indices[i][1]，分別表示對 m x n 的矩陣的第 indices[i][0] 行和第 indices[i][1] 列進行加一操作。

在執行完所有?indices?指定的增量操作后，返回矩陣中 奇數值單元格 的數目。

需要注意行和列重疊的地方是累計加的

解題思路分析

觀察題目數據范圍較小，采用較為暴力的模擬也是可以通過的，但是我們這里按照進階的標準來進行解題，時間復雜度為?O(n + m + indices.length)?且僅用?O(n + m)?額外空間的算法來解決此問題。

考慮到對于每一行和每一列來說，如果在?indices?中出現偶數次那么就相當于沒有出現，所以我們可以統計在?indices?中行和列出現奇數的次數，這里令統計好的行和列分別記為：

• 出現奇數次行的總和為 sumr
• 出現奇數次列的總和為 sumc 那么可以通過數學計算的方式來得出最后執行完所有?indices?指定的增量操作后，返回矩陣中 奇數值單元格 的數目。
• 因為對于統計出來出現奇數次的行和列來說，他們相交的部分為偶數次，所以只需要減去相交部分的單元格數量即可，那么最后答案就是 sumr * n + sumc * m - sumr * sumc * 2

為什么要 * 2：是因為在 sumr * n 和 sumc * m 的時候分別加了一次相交的部分，總共就是加了兩次，所以需要 * 2

具體實現

• 在統計?indices?中進行和列出現是否為奇數次時，我們可以使用兩個一維數組進行統計 sr[m] 和 sc[n]，分別表示行和列出現的次數。
• 因為我們只需統計出現奇數次的行和列，那么我們可以采用異或 ^ 運算進行優化。
• 最后統計行和列出現奇數次的個數即可。

復雜度分析

• 時間復雜度：O(n + m + indices.length)，n 和 m 分別為矩陣的長和寬，indices.length 為數組 indices 的長度。
• 空間復雜度：O(n + m)，僅需用于保存行和列的一維數組。

代碼實現

class Solution {
public:
    int oddCells(int m, int n, vector<vector<int>>& indices) {
        //統計被加上奇數次的行和列
        int sr[m], sc[n];
        memset(sr, 0, sizeof(sr));
        memset(sc, 0, sizeof(sc));
        int sumr, sumc;
        sumr = sumc = 0;
        for(auto &v : indices){
            //如果為偶數次就是 0，奇數次為 1，用異或來變化0和1
            sr[v[0]] ^= 1;
            //統計奇數次的行
            if(sr[v[0]]) sumr++;
            else sumr--;
            sc[v[1]] ^= 1;
            //統計奇數次的列
            if(sc[v[1]]) sumc++;
            else sumc--;
        }
        //奇數次行個數加上奇數次列個數，減去相交為偶數次的點，因為加了兩遍所以要 *2
        int ans = sumr * n + sumc * m - sumr * sumc * 2;
        return ans;
    }
};

總結

• 該題難點在于如何優化時間復雜度為?O(n + m + indices.length)?且僅用?O(n + m)?額外空間的算法來解決此問題。
• 通過統計行和列出現的次數便能進一步實現優化。核心思想在于計數。

測試結果：