1252. 奇数值单元格的数目 : 简单计数模拟题

站长

2023年03月25日 15:32 · 阅读数 15

题目描述

这是 LeetCode 上的 1252. 奇数值单元格的数目 ，难度为简单。

Tag : 「模拟」、「位运算」、「计数」

给你一个 m×nm \times nm×n 的矩阵，最开始的时候，每个单元格中的值都是 000。

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

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

rir_iri 行上的所有单元格，加 111 。
cic_ici 列上的所有单元格，加 111 。

给你 mmm、nnn 和 indicesindicesindices 。请你在执行完所有 indicesindicesindices 指定的增量操作后，返回矩阵中奇数值单元格的数目。

示例 1： 1252. 奇数值单元格的数目 : 简单计数模拟题

输入：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： 1252. 奇数值单元格的数目 : 简单计数模拟题

输入：m = 2, n = 2, indices = [[1,1],[0,0]]

输出：0

解释：最后的矩阵是 [[2,2],[2,2]]，里面没有奇数。

提示：

1<=m,n<=501 <= m, n <= 501<=m,n<=50
1<=indices.length<=1001 <= indices.length <= 1001<=indices.length<=100
0<=ri<m0 <= r_i < m0<=ri<m
0<=ci<n0 <= c_i < n0<=ci<n

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

基本分析

容易想到时间复杂度为 O(l+m×n)O(l + m \times n)O(l+m×n)，空间复杂度为 O(m+n)O(m + n)O(m+n) 的做法，在此不再赘述。

对于某个位置最终累加值为奇数的充要条件为「所在行被累加次数的奇偶性」与「所在列被累加次数的奇偶性」不同。

因此我们可以统计累加次数为奇数的行数 aaa（累加次数为偶数的行数为 m−am - am−a），累加次数为奇数的列数 bbb（累加次数为偶数的列数为 n−bn - bn−b），根据乘法原理，最终答案为 a×(n−b)+(m−a)×ba \times (n - b) + (m - a) \times ba×(n−b)+(m−a)×b。

计数模拟

由于我们只需关系某个位置的奇偶性，而不关心具体的累加值，我们可以创建两个数组 r 和 c，统计每行和每列的累加值的奇偶性。

当 r[idx]r[idx]r[idx] 为 True 含义为第 idxidxidx 行的累加值为奇数，否则为偶数。列数组 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 a * (n - b) + (m - a) * b;
    }
}

时间复杂度：构建计数数组的复杂度为 O(m+n)O(m + n)O(m+n)，统计奇数行和奇数列复杂度为 O(l)O(l)O(l)，其中 lll 为数组 ins 的长度，复杂度为 O(m+n+l)O(m + n + l)O(m+n+l)
空间复杂度：O(m+n)O(m + n)O(m+n)

位运算

更进一步，我们可以使用两个 long 变量 c1c1c1 和 c2c2c2 来分别充当行和列的计数数组，当 c1c1c1 的第 kkk 位为 111，代表第 kkk 行累加值为奇数，当 c1c1c1 的第 kkk 位为 000，代表第 kkk 行累加值为偶数；c2c2c2 的计数规则同理。而翻转二进制中的某一位可使用「异或」操作。

当处理完所有的 ins 之后，可通过「遍历 c1c1c1 的低 mmm 位 + 遍历 c2c2c2 的低 nnn 位」来得到行数中奇数个数 aaa，列数中奇数个数 bbb，复杂度为 O(m+n)O(m + n)O(m+n)；也使用 bitCount 统计 long 二进制数中 111 的个数（本质是分治操作），复杂度为 O(log⁡64)O(\log{64})O(log64)。

代码：

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 a * (n - b) + (m - a) * b;
    }
}

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 a * (n - b) + (m - a) * b;
    }
}

时间复杂度：处理所有的 ins 复杂度为 O(l)O(l)O(l)，其中 lll 为数组 ins 的长度；使用遍历方式统计奇数行和奇数列个数复杂度为 O(m+n)O(m + n)O(m+n)；使用 bitCount 操作统计二进制中 111 个数，复杂度为 O(log⁡C)O(\log{C})O(logC)，其中 C=64C = 64C=64 为 long 二进制数长度，整体复杂度为 O(l+m+n)O(l + m + n)O(l+m+n) 或 O(l+log⁡C)O(l + \log{C})O(l+logC)
空间复杂度：O(1)O(1)O(1)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1252 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。