C++算法實現leetcode 1252奇數值單元格數目
題目描述
題目鏈接: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) 額外空間的算法來解決此問題。
- 通過統計行和列出現的次數便能進一步實現優化。核心思想在於計數。
測試結果:
以上就是C++實現leetcode 1252奇數值單元格的數目題解的詳細內容,更多關於C++奇數值單元格的數目的資料請關註WalkonNet其它相關文章!
推薦閱讀:
- Java C++ 算法leetcode828統計子串中唯一字符乘法原理
- C++實現LeetCode(347.前K個高頻元素)
- C++實現LeetCode(149.共線點個數)
- 詳解C語言中雙指針算法的使用
- C++實現LeetCode(209.最短子數組之和)