22｜位元集合

還沒完成C 或 C++ 皆可CPU 時間上限 2 秒記憶體預算 139264 bytes

相關主題： 控制記憶體的必備指令

注意

這一題還沒有筆記。

題目說明

C 或 C++ 皆可｜CPU 時間上限 2 秒｜記憶體預算 139264 bytes（136 KB，heap + 全域/靜態資料 + stack 合計）

題目

給你 n 個介於 0 到 2^20 - 1（也就是 1048575）之間的整數，可能有重複。請回答兩個問題：

1. 一共出現了幾種不同的數字？
2. 在 0 到 1048575 之中，沒有出現過的數字裡最小的是哪一個？

兩個問題都需要記住「每個數字有沒有出現過」，而數字有 2^20 = 1048576 種可能。常見的寫法都太大了：

• bool seen[1048576]：每個數字佔 1 byte，共 1048576 bytes（1 MB）。
• std::set / std::unordered_set：只存出現過的數字，但每個元素還要額外的指標和節點，200000 個數字要 5 MB 以上。
• 把數字存進陣列再排序：200000 個 int 要 800000 bytes。

可是「有沒有出現過」只有「是」和「否」兩種答案，1 個位元就夠了。1 個 byte 有 8 個位元，可以記 8 個數字，所以 2^20 個數字只要 2^20 / 8 = 131072 bytes（128 KB）。這種一個位元代表一個元素的資料結構叫做位元集合（bitset）。

這一題的預算 136 KB = 128 KB 的位元集合 + 8 KB 的餘裕。

輸入

• 第一行是一個整數 n（1 ≤ n ≤ 200000）。
• 第二行有 n 個整數 x（0 ≤ x ≤ 1048575），數字之間用一個空格隔開，可能有重複。

輸出

輸出兩行：

1. 第一行：不同數字的個數。
2. 第二行：0 到 1048575 之中，沒有出現在輸入裡的最小數字。（因為 n ≤ 200000，比 1048576 小，這個數字一定存在。）

範例

輸入：

8
3 0 1 3 7 1 2 9

輸出：

6
4

出現過的數字是 0、1、2、3、7、9，共 6 種（3 和 1 各出現兩次，只算一次）。0、1、2、3 都出現了，4 沒有出現，所以第二行是 4。

記憶體預算怎麼算

檢查時會把下面三項加起來，合計不能超過 139264 bytes：

項目	包含什麼
heap 最高用量	執行期間「同一時間還沒釋放」的 malloc / calloc / realloc / new 的最大總量，包含 std::vector、std::set 等標準函式庫容器在內部配置的記憶體
全域 / 靜態資料	全域變數、static 變數（例如全域的位元陣列），加上常數和字串常值
stack 最深用量（約）	區域變數（例如 main 裡的陣列）、函式呼叫，以及 scanf / printf 等函式內部用到的 stack。程式啟動和最基本的輸入輸出本身用掉的部分（約 5 KB）會自動扣掉

C 執行環境內部的輸入輸出緩衝區不計算。檢查結果最後的「記憶體預算」會列出這三項各用了多少。

位元集合放在哪裡都可以，用量都是 128 KB 左右：

• 全域陣列（算在「全域 / 靜態資料」，而且一開始自動全部是 0）
• calloc、new、std::vector<bool>、std::make_unique<std::bitset<...>>()（算在 heap，記得釋放）
• std::bitset<1 << 20> 放在全域或 main 裡

要注意的地方：

• 不要把 1 MB 的陣列宣告成區域變數：stack 總共只有 1 MB，程式會直接 stack overflow（第一階段的 Sanitizer 會顯示 stack-overflow）。128 KB 的區域陣列放得下，但大陣列放全域比較保險。
• C++20 的 std::format 會把約 12.5 KB 的 Unicode 表格放進你的程式（算在「常數與字串」），128 KB + 12.5 KB 會超過預算。輸出請用 std::cout 或 printf。

複習重點

C：

• 位元運算子：&（AND）、|（OR）、<<（左移）、>>（右移）
• 對非負整數：x >> 3 等於 x / 8，x & 7 等於 x % 8；x >> 5 等於 x / 32，x & 31 等於 x % 32
• 用無號整數做位元運算（1u << k），避免 1 << 31 這種有號整數溢位
• 大陣列放在全域（自動清成 0）或用 calloc 配置

C++：

• std::bitset<N>（<bitset>）：b[x] 讀寫第 x 個位元，b.count() 數有幾個 1
• std::vector<bool>：標準函式庫的特化版本，每個元素只佔 1 個位元
• 上面 C 的位元運算子在 C++ 也一樣能用

提示 1：要準備多大的空間？

每個數字只需要 1 個位元（0 = 沒出現過，1 = 出現過）。

• C：unsigned char 陣列，長度 2^20 / 8 = 131072；或 unsigned int（32 位元）陣列，長度 2^20 / 32 = 32768。放在全域，一開始就全部是 0。
• C++：可以直接用 std::bitset<(1 << 20)> 或 std::vector<bool> seen(1 << 20)，它們內部就是這樣存的。

提示 2：怎麼找到數字 x 的那個位元？

以 byte（8 個位元）為單位時，數字 x 記在第 x >> 3 個 byte 的第 x & 7 個位元。例如 x = 13：13 >> 3 是 1、13 & 7 是 5，所以是第 1 個 byte 的第 5 個位元（都從 0 開始數）。

	以 8 位元（unsigned char）為單位	以 32 位元（unsigned int）為單位
在陣列的第幾格	x >> 3	x >> 5
這一格裡的第幾個位元	x & 7	x & 31
遮罩（只有那個位元是 1）	1u << (x & 7)	1u << (x & 31)

有了遮罩，就能用 | 把位元設成 1，用 >> 和 & 把位元讀出來（以 8 位元為單位）：

a[x >> 3] |= 1u << (x & 7);           // 把 x 的位元設成 1，同一格的其他 7 個位元不受影響
int bit = (a[x >> 3] >> (x & 7)) & 1;  // 讀出 x 的位元：0 或 1

遮罩要寫 1u（無號），不要寫 1：在 C 裡 1 << 31 超出 int 的範圍，是未定義行為，Sanitizer 會抓到。（C++20 雖然規定了它的結果，但寫 1u 在兩種語言都清楚又安全。）

可以把「設成 1」和「讀出來」各包成一個小函式，主程式會好讀很多。

提示 3：兩個答案怎麼算？

• 不同數字的個數：讀到 x 時，如果它的位元還是 0，代表第一次看到它，計數加 1 再把位元設成 1；已經是 1 的就是重複，不用算。（C++ 也可以全部讀完後用 b.count()。）
• 沒出現過的最小數字：從 0 開始往上，找第一個位元是 0 的數字。因為 n < 2^20，一定會在範圍內找到，不會超出陣列。

讀數字的時候不需要把它存起來，設好位元就可以丟掉了。