📘 題目敘述
你有一個整數集合 s，原本應該包含從 1 到 n 的所有數字。
但因為某個錯誤，其中一個數字被重複成了另一個數字，結果就變成：
- 有一個數字出現了兩次
- 有一個數字消失了
現在給你一個整數陣列 nums，表示發生錯誤之後的結果。
請找出：
- 哪個數字出現了兩次
- 哪個數字缺失了
並以陣列形式回傳。
條件限制
2 <= nums.length <= 10^41 <= nums[i] <= 10^4
🧠 解題思路
我這份寫法是先排序，讓相同的數字會排在一起，接著一邊掃描，一邊找：
- 哪個數字重複了
- 哪個數字本來應該出現，卻沒有出現
先想正常情況。
如果沒有出錯，排序後應該會長成：
1, 2, 3, 4, ..., n
所以我用一個 missing 來表示：
我目前預期應該看到的數字是誰。
一開始 missing = 1，代表我先期待看到 1。
如果某個數字 i 剛好等於 missing，就表示這個數字有正常出現，那我就把 missing++，繼續期待下一個數字。
而重複數字這邊，我用：
twice：先記目前看到的那個候選數字check：表示我有沒有正式確認重複數字已經出現第二次
因為排序後，相同數字會排在一起，所以當某個數字第二次出現時，就可以知道它是重複的數字。
這份程式的核心想法就是：
排序後，
missing負責追目前應該出現卻還沒被推過去的數字，twice則負責記錄哪個數字重複出現。
所有變數
missing：目前預期應該看到的數字，最後會停在缺失的數字twice：出現兩次的數字check：是否已經確認重複數字
🪜 主要流程步驟
1. 先把 nums 排序
sort(nums.begin(), nums.end());
先排序之後，相同數字就會靠在一起，比較容易看出誰重複了。
而且排序完也會比較接近原本正常應該有的順序：
1, 2, 3, 4, ...
所以也方便一路追哪個數字不見了。
2. 初始化 missing、twice、check
int missing = 1;
int twice = 0;
bool check = false;
這三個變數的角色是：
missing = 1- 一開始先期待看到
1
- 一開始先期待看到
twice = 0- 先表示目前還沒記到任何重複數字
check = false- 代表目前還沒正式確認哪個數字是重複的
3. 掃過排序後的 nums，如果數字符合 missing，就把 missing 往後推
if (i == missing) {
missing++;
}
這段的意思是：
如果目前看到的數字 i，剛好就是我現在預期的 missing，那代表這個數字沒有缺失，有正常出現，所以我就改成期待下一個數字。
例如：
- 一開始
missing = 1 - 看到
1，就把missing變成2 - 接著看到
2，就把missing變成3
所以 missing 會一路被推進。
4. 用 twice 和 check 找出重複數字
if (i != twice && !check) {
twice = i;
} else {
check = true;
}
這段是在做重複數字的判斷。
它的運作方式是：
- 如果目前還沒正式確認重複數字，而且現在的
i跟twice不同- 就先把
twice改成現在這個數字
- 就先把
- 否則
- 代表同一個數字又出現了一次
- 這時就知道它是重複數字，把
check = true
因為排序後，相同數字會連在一起，所以當某個值第二次出現時，這邊就能抓到。
5. 為什麼最後 missing 會停在缺失的數字
這份程式裡，missing 只有在「目前看到的數字剛好等於它」時才會往後加。
所以如果某個數字缺了，missing 就卡在那裡過不去。
例如：
nums = [1,2,2,4]- 排序後還是
[1,2,2,4]
掃描過程：
- 看到
1，missing從1變2 - 看到
2，missing從2變3 - 再看到
2，因為2 != 3，所以missing不動 - 看到
4，因為4 != 3，所以missing還是不動
最後 missing = 3，就是不見的數字。
6. 最後回傳 {twice, missing}
return {twice, missing};
題目要回傳的是：
- 第一個位置：重複的數字
- 第二個位置：缺失的數字
所以最後直接回傳 {twice, missing}。
⏱️ 複雜度
設 n = nums.length。
- 時間複雜度：
O(n log n)
排序需要O(n log n)，後面掃描一次是O(n)，所以整體由排序主導。 - 空間複雜度：
O(log n)
這裡把排序遞迴堆疊所需空間算進去。
💻 程式碼實作
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
sort(nums.begin(), nums.end());
int missing = 1;
int twice = 0;
bool check = false;
for (int i : nums) {
if (i == missing) {
missing++;
}
if (i != twice && !check) {
twice = i;
} else {
check = true;
}
}
return {twice, missing};
}
};