奇數(shù)值單元格的數(shù)目

題目描述

給你一個(gè) n 行 m 列的矩陣，最開始的時(shí)候，每個(gè)單元格中的值都是 0。

另有一個(gè)索引數(shù)組 indices，indices[i] = [ri, ci] 中的 ri 和 ci 分別表示指定的行和列（從 0 開始編號(hào)）。

你需要將每對(duì) [ri, ci] 指定的行和列上的所有單元格的值加 1。

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

示例 1:

示例圖1

輸入：n = 2, m = 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:

示例圖2

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

提示：

• 1 <= n <= 50
• 1 <= m <= 50
• 1 <= indices.length <= 100
• 0 <= indices[i][0] < n
• 0 <= indices[i][1] < m

解題思路

首先，使用兩個(gè)數(shù)組來分別記錄行和列中各自的奇數(shù)個(gè)數(shù)，然后將行列中奇數(shù)個(gè)數(shù)相加然后減去重疊的部分即可得到答案。

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(m + n)。
• 空間復(fù)雜度：O(m + n)。

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

class Solution {
    public int oddCells(int n, int m, int[][] indices) {
        boolean[] row = new boolean[n];
        boolean[] col = new boolean[m];

        for(int i = 0; i < indices.length; i ++){
            row[indices[i][0]] = !row[indices[i][0]];
            col[indices[i][1]] = !col[indices[i][1]];
        }

        int rowCount = 0, colCount = 0;
        for(int i = 0; i < row.length; i ++) {
            if(row[i]) {
                rowCount ++;
            }
        }

        for(int i = 0; i < col.length; i ++){
            if(col[i]) {
                colCount ++;
            }
        }
        
        return rowCount * m + colCount * n - rowCount * colCount * 2;
    }
}