2166-设计位集

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

位集 Bitset 是一种能以紧凑形式存储位的数据结构。

请你实现 Bitset 类。

  • Bitset(int size) 用 size 个位初始化 Bitset ，所有位都是 0 。
  • void fix(int idx) 将下标为 idx 的位上的值更新为 1 。如果值已经是 1 ，则不会发生任何改变。
  • void unfix(int idx) 将下标为 idx 的位上的值更新为 0 。如果值已经是 0 ，则不会发生任何改变。
  • void flip() 翻转 Bitset 中每一位上的值。换句话说，所有值为 0 的位将会变成 1 ，反之亦然。
  • boolean all() 检查 Bitset 中 每一位 的值是否都是 1 。如果满足此条件，返回 true ；否则，返回 false 。
  • boolean one() 检查 Bitset 中 是否 至少一位 的值是 1 。如果满足此条件，返回 true ；否则，返回 false 。
  • int count() 返回 Bitset 中值为 1 的位的 总数 。
  • String toString() 返回 Bitset 的当前组成情况。注意，在结果字符串中，第 i 个下标处的字符应该与 Bitset 中的第 i 位一致。

示例：

**输入**
["Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"]
[[5], [3], [1], [], [], [0], [], [], [0], [], []]
**输出**
[null, null, null, null, false, null, null, true, null, 2, "01010"]

**解释**
Bitset bs = new Bitset(5); // bitset = "00000".
bs.fix(3);     // 将 idx = 3 处的值更新为 1 ，此时 bitset = "00010" 。
bs.fix(1);     // 将 idx = 1 处的值更新为 1 ，此时 bitset = "01010" 。
bs.flip();     // 翻转每一位上的值，此时 bitset = "10101" 。
bs.all();      // 返回 False ，bitset 中的值不全为 1 。
bs.unfix(0);   // 将 idx = 0 处的值更新为 0 ，此时 bitset = "00101" 。
bs.flip();     // 翻转每一位上的值，此时 bitset = "11010" 。
bs.one();      // 返回 True ，至少存在一位的值为 1 。
bs.unfix(0);   // 将 idx = 0 处的值更新为 0 ，此时 bitset = "01010" 。
bs.count();    // 返回 2 ，当前有 2 位的值为 1 。
bs.toString(); // 返回 "01010" ，即 bitset 的当前组成情况。

提示：

  • 1 <= size <= 105
  • 0 <= idx <= size - 1
  • 至多调用 fix、unfix、flip、all、one、count 和 toString 方法 总共 105 次
  • 至少调用 all、one、count 或 toString 方法一次
  • 至多调用 toString 方法 5 次

方法一：利用数组实现

思路与算法

根据题意，我们需要在 O(1) 的时间复杂度内实现 fix()}, \texttt{unfix()}, \texttt{flip()}, \texttt{all()}, \texttt{one()}, \texttt{count() 方法，并在 O(n) 的时间复杂度内实现 toString() 方法。

我们首先考虑用一个长度为 size 的数组 arr 来实现 bitset，其中第 k 个元素的数值等于第 k 位的数值。它支持在 O(1) 的时间复杂度内实现 fix()}, \texttt{unfix() 这两个方法，但其他方法都需要 O(n) 来实现。

进一步地，考虑到每一次执行 fix()}, \texttt{unfix() 操作时，都最多只有一个位被翻转，因此 1 的位数最多改变 1。同时，在 flip() 操作前后 1 的位数之和即为 size。

那么我们可以用额外的整数 cnt 来维护 1 的位数。cnt 的初始值为 0，在每次更新 arr 时，我们都对应更新 cnt 的数值。基于此，我们可以在不影响其余方法的复杂度时，在 O(1) 的时间复杂度内实现 all()}, \texttt{one()}, \texttt{count() 这三个方法。

至此，我们只剩 flip() 方法的复杂度不符合要求。由于反转两次等于不变，且反转和赋值操作可交换，因此我们也可以通过一个二进制位 reversed 来表示反转操作的次数奇偶性。reversed 的初值为 0；在每次 flip() 时，我们可以通过对 reversed 与 1 取异或来代替翻转整个数组。除此以外，第 k 位的数值即为 arr}[k] \oplus \textit{reversed，其中 \oplus 为按位异或。同理，在执行某一位赋值操作时，如果该位的数值会发生变化，我们只需要将该数值与 1 取异或即可。

按照上面的方法，我们就可以在不影响其余操作的时间复杂度下，将 flip() 方法的复杂度也降低为 O(1)。

综上，我们可以通过以下三个元素来实现 Bitset 类：

  • arr：长度为 size 的数组，用来存储每一位的取值；

  • cnt：整数，用来统计 1 的位数；

  • reversed：二进制位，用来统计反转操作的次数奇偶性。

各个方法的具体实现详见代码。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Bitset {
private:
    vector<int> arr;   // 存储每一位的数组
    int cnt = 0;   // 1 的个数
    int reversed = 0;   // 反转操作的次数奇偶性
public:
    Bitset(int size) {
        arr.resize(size);
        cnt = 0;
        reversed = 0;
    }
    
    void fix(int idx) {
        if ((arr[idx] ^ reversed) == 0) {
            arr[idx] ^= 1;
            ++cnt;
        }
    }
    
    void unfix(int idx) {
        if ((arr[idx] ^ reversed) == 1) {
            arr[idx] ^= 1;
            --cnt;
        }
    }
    
    void flip() {
        reversed ^= 1;
        cnt = arr.size() - cnt;
    }
    
    bool all() {
        return cnt == arr.size();
    }
    
    bool one() {
        return cnt > 0;
    }
    
    int count() {
        return cnt;
    }
    
    string toString() {
        string res;
        for (int bit: arr) {
            res.push_back('0' + (bit ^ reversed));
        }
        return res;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Bitset:

    def __init__(self, size: int):
        self.arr = [0] * size   # 存储每一位的数组
        self.cnt = 0   # 1 的个数
        self.reversed = 0   # 反转操作的次数奇偶性

    def fix(self, idx: int) -> None:
        if self.arr[idx] ^ self.reversed == 0:
            self.arr[idx] ^= 1
            self.cnt += 1

    def unfix(self, idx: int) -> None:
        if self.arr[idx] ^ self.reversed == 1:
            self.arr[idx] ^= 1
            self.cnt -= 1

    def flip(self) -> None:
        self.reversed ^= 1
        self.cnt = len(self.arr) - self.cnt

    def all(self) -> bool:
        return self.cnt == len(self.arr)

    def one(self) -> bool:
        return self.cnt > 0

    def count(self) -> int:
        return self.cnt

    def toString(self) -> str:
        res = ""
        for bit in self.arr:
            res += str(bit ^ self.reversed) 
        return res

复杂度分析

  • 时间复杂度：O(k_1n + k_2)，其中 n 为位集的长度size，k_1 为 toString() 操作的次数，k_2 为其他操作的次数。预处理和单次 toString() 操作的时间复杂度均为 O(n)，其余单次操作的时间复杂度为 O(1)。

  • 空间复杂度：O(n)，即为辅助数组的空间开销。

 Comments
On this page
2166-设计位集