12｜排序與去重

還沒完成只限 C++CPU 時間上限 1 秒

題目說明

只限 C++｜CPU 時間上限 1 秒

題目

讀入一堆整數（事先不知道有幾個），把重複的去掉，再由小到大輸出還剩下的不同數值，並輸出一共有幾個不同的數值。

這一題要練習 C++ 標準函式庫裡最常用的三樣東西：std::vector（會自己長大的陣列）、std::sort（排序）、std::unique 搭配 erase（去掉重複）。用 C 寫的話，要自己用 malloc/realloc 管理一塊會變大的陣列、用 qsort 加上自己寫的比較函式排序、再寫一個迴圈去重；C++ 幾行就做完了。

資料最多有 20 萬個。如果每讀一個數字，就在已經存下來的結果裡從頭找一遍「有沒有出現過」，最大的測試資料要比較幾十億次，會超過時間；先排序再去重只要 O(n log n)。

輸入

一些整數，一直讀到輸入結束 (EOF)。至少 1 個，最多 200000 個。
每個整數 x 都滿足 -10^9 ≤ x ≤ 10^9。
整數之間用空白分隔：可能是一個或多個空格、Tab 或換行，也可能有空行。每行有幾個整數不固定。

輸出

一共 2 行：

第 1 行：不同的數值有幾個。
第 2 行：這些不同的數值，由小到大排列，用一個空格分隔。

範例

輸入：

5 3 -2 5 0
3 3 -2
8

輸出：

5
-2 0 3 5 8

輸入共有 9 個整數，去掉重複後剩下 -2、0、3、5、8 這 5 個。

複習重點

C++：

std::vector<int> v; 加上 v.push_back(x);：不用事先知道資料有幾筆，空間不夠時 vector 會自動擴充
while (std::cin >> x)：讀到 EOF 或讀不到整數時條件會變成 false，迴圈就結束；>> 會自動跳過空格、Tab 和換行
std::sort(v.begin(), v.end());（在 <algorithm>）：由小到大排序
std::unique(v.begin(), v.end())：把相鄰的重複元素移掉，回傳「新結尾」的位置，但不會改變 vector 的大小，所以要搭配 v.erase(新結尾, v.end()) 真正刪掉後面那段
資料量大的時候，習慣在 main 一開始加上 std::ios::sync_with_stdio(false); 和 std::cin.tie(nullptr);，在很多編譯器上可以讓 cin/cout 快不少

對照 C：

讀到 EOF 的寫法是 while (scanf("%d", &x) == 1)
會變大的陣列要自己用 malloc 配置、滿了用 realloc 加倍，最後還要 free
排序用 qsort(a, n, sizeof(int), cmp)，比較函式要接收 const void* 再自己轉型
去重要自己寫迴圈：排序後只保留「和前一個不一樣」的元素

提示 1：怎麼讀到輸入結束？

std::vector<int> v;
int x;
while (std::cin >> x) {
    v.push_back(x);
}

在終端機手動測試時，打完數字後按 Ctrl+Z 再按 Enter 代表輸入結束。

讀 200000 個整數時，建議在 main 的第一行加上：

std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

第一行讓 cin/cout 不必和 C 的 scanf/printf 保持同步（加了之後就不要混用兩種），第二行讓 cin 每次讀之前不用先清空 cout。

提示 2：為什麼要先排序才能用 std::unique？

std::unique 只會處理「連在一起的重複」，例如 3 3 5 3 只會變成 3 5 3。先排序之後，相同的數值一定會排在一起，std::unique 就能把所有重複都去掉。

另外要注意 std::unique 不會讓 vector 變短：它把要留下的元素往前搬，回傳新結尾的位置。後面那段要用 erase 刪掉：

auto new_end = std::unique(v.begin(), v.end());
v.erase(new_end, v.end());

提示 3：另一種做法：std::set

std::set<int>（在 <set>）是「自動排序、不允許重複」的容器。把每個數字 insert 進去，最後用範圍 for 迴圈走一遍，就已經是由小到大、沒有重複，而 s.size() 就是不同數值的個數。

兩種做法都可以通過。set 寫起來更短，但每次插入都要找位置，資料量大時通常比「vector + sort + unique」慢一些。有興趣的話兩種都寫寫看。