輸入：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 個(gè)奇數(shù)。

示例 2：

輸入： m = 2, n = 2, indices = [[1,1],[0,0]]
輸出： 0
解釋：最后的矩陣是 [[2,2],[2,2]]，里面沒有奇數(shù)。

整理題意

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

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

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

解題思路分析

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

考慮到對(duì)于每一行和每一列來說，如果在 indices 中出現(xiàn)偶數(shù)次那么就相當(dāng)于沒有出現(xiàn)，所以我們可以統(tǒng)計(jì)在 indices 中行和列出現(xiàn)奇數(shù)的次數(shù)，這里令統(tǒng)計(jì)好的行和列分別記為：

出現(xiàn)奇數(shù)次行的總和為 sumr
出現(xiàn)奇數(shù)次列的總和為 sumc 那么可以通過數(shù)學(xué)計(jì)算的方式來得出最后執(zhí)行完所有 indices 指定的增量操作后，返回矩陣中 奇數(shù)值單元格 的數(shù)目。
因?yàn)閷?duì)于統(tǒng)計(jì)出來出現(xiàn)奇數(shù)次的行和列來說，他們相交的部分為偶數(shù)次，所以只需要減去相交部分的單元格數(shù)量即可，那么最后答案就是 sumr * n + sumc * m - sumr * sumc * 2

為什么要 * 2：是因?yàn)樵?sumr * n 和 sumc * m 的時(shí)候分別加了一次相交的部分，總共就是加了兩次，所以需要 * 2

具體實(shí)現(xiàn)

在統(tǒng)計(jì) indices 中進(jìn)行和列出現(xiàn)是否為奇數(shù)次時(shí)，我們可以使用兩個(gè)一維數(shù)組進(jìn)行統(tǒng)計(jì) sr[m] 和 sc[n]，分別表示行和列出現(xiàn)的次數(shù)。
因?yàn)槲覀冎恍杞y(tǒng)計(jì)出現(xiàn)奇數(shù)次的行和列，那么我們可以采用異或 ^ 運(yùn)算進(jìn)行優(yōu)化。
最后統(tǒng)計(jì)行和列出現(xiàn)奇數(shù)次的個(gè)數(shù)即可。

復(fù)雜度分析

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

代碼實(shí)現(xiàn)

class Solution {
public:
    int oddCells(int m, int n, vector<vector<int>>& indices) {
        //統(tǒng)計(jì)被加上奇數(shù)次的行和列
        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){
            //如果為偶數(shù)次就是 0，奇數(shù)次為 1，用異或來變化0和1
            sr[v[0]] ^= 1;
            //統(tǒng)計(jì)奇數(shù)次的行
            if(sr[v[0]]) sumr++;
            else sumr--;
            sc[v[1]] ^= 1;
            //統(tǒng)計(jì)奇數(shù)次的列
            if(sc[v[1]]) sumc++;
            else sumc--;
        }
        //奇數(shù)次行個(gè)數(shù)加上奇數(shù)次列個(gè)數(shù)，減去相交為偶數(shù)次的點(diǎn)，因?yàn)榧恿藘杀樗砸?*2
        int ans = sumr * n + sumc * m - sumr * sumc * 2;
        return ans;
    }
};

總結(jié)

該題難點(diǎn)在于如何優(yōu)化時(shí)間復(fù)雜度為 O(n + m + indices.length) 且僅用 O(n + m) 額外空間的算法來解決此問題。
通過統(tǒng)計(jì)行和列出現(xiàn)的次數(shù)便能進(jìn)一步實(shí)現(xiàn)優(yōu)化。核心思想在于計(jì)數(shù)。

測試結(jié)果：