題目描述
這是 LeetCode 上的 1252. 奇數值單元格的數目 ，難度為 簡單。
Tag : 「模拟」、「位運算」、「計數」
給你一個 的矩陣，最開始的時候，每個單元格中的值都是 。
另有一個二維索引數組
indices
， 指向矩陣中的某個位置，其中 和 分别表示指定的行和列（從
對
- 行上的所有單元格，加
- 列上的所有單元格，加
給你 、 和 。請你在執行完所有
示例 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]]，裡面沒有奇數。 提示：
進階：你可以設計一個時間複雜度為 且僅用
基本分析
容易想到時間複雜度為 ，空間複雜度為
對于某個位置最終累加值為奇數的充要條件為「所在行被累加次數的奇偶性」與「所在列被累加次數的奇偶性」不同。
是以我們可以統計累加次數為奇數的行數 （累加次數為偶數的行數為 ），累加次數為奇數的列數 （累加次數為偶數的列數為 ），根據乘法原理，最終答案為 。
計數模拟
由于我們隻需關系某個位置的奇偶性，而不關心具體的累加值，我們可以建立兩個數組
r
和
c
，統計每行和每列的累加值的奇偶性。
當 為
True
含義為第 行的累加值為奇數，否則為偶數。列數組
c
的統計規則同理。
代碼：
class Solution {
public int oddCells(int m, int n, int[][] ins) {
boolean[] r = new boolean[m], c = new boolean[n];
int a = 0, b = 0;
for (int[] info : ins) {
a += (r[info[0]] = !r[info[0]]) ? 1 : -1;
b += (c[info[1]] = !c[info[1]]) ? 1 : -1;
}
return - 時間複雜度：建構計數數組的複雜度為，統計奇數行和奇數列複雜度為，其中為數組
ins
- 空間複雜度：
位運算
更進一步，我們可以使用兩個
long
變量 和 來分别充當行和列的計數數組，當 的第 位為 ，代表第 行累加值為奇數，當 的第 位為 ，代表第 行累加值為偶數；
當處理完所有的
ins
之後，可通過「周遊 的低 位 + 周遊 的低 位」來得到行數中奇數個數 ，列數中奇數個數 ，複雜度為 ；也使用
bitCount
統計
long
二進制數中 的個數（本質是分治操作），複雜度為 。
代碼：
class Solution {
public int oddCells(int m, int n, int[][] ins) {
long c1 = 0, c2 = 0;
for (int[] info : ins) {
c1 ^= 1L << info[0];
c2 ^= 1L << info[1];
}
int a = 0, b = 0;
for (int i = 0; i < m; i++) a += ((c1 >> i) & 1);
for (int i = 0; i < n; i++) b += ((c2 >> i) & 1);
return class Solution {
public int oddCells(int m, int n, int[][] ins) {
long c1 = 0, c2 = 0;
for (int[] info : ins) {
c1 ^= 1L << info[0];
c2 ^= 1L << info[1];
}
int a = Long.bitCount(c1), b = Long.bitCount(c2);
return - 時間複雜度：處理所有的
ins
ins
bitCount
long
- 空間複雜度：
最後
這是我們「刷穿 LeetCode」系列文章的第
No.1252
篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。
在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。