『LeetCode』1252 奇数值单元格的数目

题目

给你一个 m x n 的矩阵，最开始的时候，每个单元格中的值都是 0。

另有一个二维索引数组 indices，indices[i] = [ri, ci] 指向矩阵中的某个位置，其中 ri 和 ci 分别表示指定的行和列（从 0 开始编号）。

对 indices[i] 所指向的每个位置，应同时执行下述增量操作：

r^{i} 行上的所有单元格，加 1 。
c^{i} 列上的所有单元格，加 1 。

给你 m、n 和 indices 。请你在执行完所有 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]]，里面没有奇数。

提示：

\(1 <= m, n <= 50\)
\(1 <= indices.length <= 100\)
\(0 <= r_{i} < m\)
\(0 <= c_{i} < n\)

进阶：你可以设计一个时间复杂度为 O(n + m + indices.length) 且仅用 O(n + m) 额外空间的算法来解决此问题吗？

题解

【奇数值单元格的数目】模拟&数学

模拟

依照题意使用一个二维矩阵模拟即可

# Code language: Python
class Solution:
    def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
        mat = [[0 for _ in range(n)] for _ in range(m)]
        for r, c in indices:
            for i in range(n):
                mat[r][i] += 1
            for i in range(m):
                mat[i][c] += 1
        return sum(c % 2 == 1 for r in mat for c in r)

// Code language: Java
class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        int[][] mat = new int[m][n];
        for (int i = 0, size = indices.length; i < size; ++i) {
            int r = indices[i][0], c = indices[i][1];
            for (int j = 0; j < m; ++j) mat[j][c]++;
            for (int j = 0; j < n; ++j) mat[r][j]++;
        }
        int cnt = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] % 2 == 1) ++cnt;
            }
        }
        return cnt;
    }
}

// Code language: C++
class Solution {
public:
    int oddCells(int m, int n, vector<vector<int>>& indices) {
        vector<vector<int>> mat(m, vector<int>(n));
        for (int i = 0, size = indices.size(); i < size; ++i) {
            int r = indices[i][0], c = indices[i][1];
            for (int j = 0; j < m; ++j) mat[j][c]++;
            for (int j = 0; j < n; ++j) mat[r][j]++;
        }
        int cnt = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] % 2 == 1) ++cnt;
            }
        }
        return cnt;
    }
};

/** Code language: JavaScript
 * @param {number} m
 * @param {number} n
 * @param {number[][]} indices
 * @return {number}
 */
var oddCells = function(m, n, indices) {
    var mat = new Array(m).fill(0).map(() => new Array(n).fill(0));
    for (let i = 0, size = indices.length; i < size; ++i) {
        let r = indices[i][0], c = indices[i][1];
        for (let j = 0; j < m; ++j) mat[j][c]++;
        for (let j = 0; j < n; ++j) mat[r][j]++;
    }
    let cnt = 0;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (mat[i][j] % 2 == 1) ++cnt;
        }
    }
    return cnt;
};

时间复杂度: \(O(k \times (n + m) + nm)\), \(n, m\) 表示矩阵的列数和行数, \(k\) 表示 indices 的长度
空间复杂度: \(O(nm)\)

数学

注意到处理都是整行整列进行的，所以也可以只记录各行各列的累加数量，最后统计即可。

由小学数学知识可知，两个正整数相加，当且仅当其中一个数为奇数，另一个数为偶数时结果为奇数。

所以最终结果为 \((行为奇数 \times 列为偶数) + (行为偶数 \times 列为奇数)\).

# Code language: Python
class Solution:
    def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
        row = [0 for _ in range(m)]
        col = [0 for _ in range(n)]

        for r, c in indices:
            row[r] += 1
            col[c] += 1
        
        a = sum(r % 2 == 1 for r in row)
        b = len(row) - a
        c = sum(c % 2 == 1 for c in col)
        d = len(col) - c
        return a * d + b * c

// Code language: Java
class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        int[] row = new int[m], col = new int[n];
        for (int i = 0, size = indices.length; i < size; ++i) {
            int r = indices[i][0], c = indices[i][1];
            row[r]++; col[c]++;
        }
        int a = 0, b = 0;
        for (int i = 0; i < m; ++i) if (row[i] % 2 == 1) ++a;
        for (int i = 0; i < n; ++i) if (col[i] % 2 == 1) ++b;
        return a * (n - b) + (m - a) * b;
    }
}

// Code language: C++
class Solution {
public:
    int oddCells(int m, int n, vector<vector<int>>& indices) {
        vector<int> row(m), col(n);
        for (int i = 0, size = indices.size(); i < size; ++i) {
            int r = indices[i][0], c = indices[i][1];
            row[r]++; col[c]++;
        }
        int a = 0, b = 0;
        for (int i = 0; i < m; ++i) if (row[i] % 2 == 1) ++a;
        for (int i = 0; i < n; ++i) if (col[i] % 2 == 1) ++b;
        return a * (n - b) + (m - a) * b;
    }
};

/** Code language: JavaScript
 * @param {number} m
 * @param {number} n
 * @param {number[][]} indices
 * @return {number}
 */
var oddCells = function(m, n, indices) {
    const row = Array(m).fill(0), col = Array(n).fill(0);
    for (let i = 0, size = indices.length; i < size; ++i) {
        let r = indices[i][0], c = indices[i][1];
        row[r]++; col[c]++;
    }
    let a = 0, b = 0;
    for (let i = 0; i < m; ++i) if (row[i] % 2 == 1) ++a;
    for (let i = 0; i < n; ++i) if (col[i] % 2 == 1) ++b;
    return a * (n - b) + (m - a) * b;
};

时间复杂度: \(O(k + n + m)\), \(n, m\) 表示矩阵的列数和行数, \(k\) 表示 indices 的长度
空间复杂度: \(O(n + m)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』1252 奇数值单元格的数目

题目

标签

题解

模拟

数学