題目鏈接：[Leetcode]448.找到所有數(shù)組中消失的數(shù)字
題干
給定一個范圍在 1 ≤ a[i] ≤ n ( n = 數(shù)組大小 ) 的 整型數(shù)組恩沛，數(shù)組中的元素一些出現(xiàn)了兩次腺逛，另一些只出現(xiàn)一次枪汪。
找到所有在 [1, n] 范圍之間沒有出現(xiàn)在數(shù)組中的數(shù)字顿膨。
特殊要求
您能在不使用額外空間且時間復(fù)雜度為O(n)的情況下完成這個任務(wù)嗎? 你可以假定返回的數(shù)組不算在額外空間內(nèi)翅雏。
暴力思路
利用O(n)的空間存儲結(jié)果揣云，然后遍歷一遍做標(biāo)記，便利第二遍獲得結(jié)果斜筐。然而這個思路不符合特殊要求的沒有額外空間
正確思路
這道題要做的龙致，是在有限空間中，使得原數(shù)組中顷链，存在兩種不同的表示方法目代。假設(shè)某索引位最終為表示方法X，則說明出現(xiàn)過嗤练，若表示方法為Y榛了，則說明未出現(xiàn)，添加到結(jié)果中煞抬。
拆分方法1：取模拆分
第一遍遍歷時霜大，對于取到的數(shù)字number，將nums[number]位數(shù)字添加n革答，則最終某個索引位數(shù)字小于n僧诚，則說明這個索引位沒有出現(xiàn)過。大致代碼如下：
// 第一遍遍歷做標(biāo)記
for(auto number : nums){
number = (number - 1) % n;
nums[number] += n;
}
// 第二遍查找結(jié)果項(xiàng)
for(int i = 0; i < n; i++){
if(nums[i] < n){
ans.push_back(i + 1);
}
}
拆分方法2：負(fù)數(shù)區(qū)分
這個方法比方法1要巧妙蝗碎，因?yàn)閷τ趎很大的情況，方法1可能存在int溢出問題旗扑。
方法2的思路是蹦骑，標(biāo)記過程中，將標(biāo)記內(nèi)容變?yōu)樨?fù)數(shù)臀防，則所有仍為正數(shù)的索引位數(shù)字即為所求眠菇。大致代碼：
for(auto number : nums){
nums[abs(number) - 1] = -abs(nums[abs(number) - 1]);
}
for(int i = 0; i < n; i++){
if(nums[i] > 0){
ans.push_back(i + 1);
}
}
