題目鏈接：645. 錯誤的集合 - 力扣（LeetCode）
集合s包含從1到n的整數。不幸的是，因為數據錯誤，導致集合里面某一個數字復制了成了集合里面的另外一個數字的值，導致集合 丟失了一個數字 并且 有一個數字重復 。
給定一個數組nums代表了集合S發生錯誤后的結果。
請你找出重復出現的整數，再找到丟失的整數，將它們以數組的形式返回。
思路解析：
本題可以考慮兩個思路：
- 數學方法
先對數組進行由小到大排序，因為缺失的數值介于前一個數值和后一個數值中間，并且在不缺失的情況下相鄰兩個數值差值為1，如果有數值重復，那么重復的數值和下一個不同的數值之間的差值為2，所以需要記錄前一個數值存儲在變量prev中
注意prev初始化為0，因為存在數組中缺失的數值為1，而如果數組中只有兩個元素，那么最大值為2，此時在數組中找不到一個數值使得重復的數值和下一個的不同兩個數值差值為2
先找到重復的數值，即下一個元素和當前元素cur相同時，存儲當前數值cur到新數組的第一個元素的位置，更新prev為當前的重復數值
再繼續循環，若當前數值與prev中存的數值差值大于1，說明此時已經找完了重復元素，因為不缺失數值時相鄰兩個數值差值為1，而此時prev中的數值和當前數值差值大于1，說明prev中的數值+1即為缺失的數值，將prev + 1存儲新數組的第二個位置后更新prev
當走完該循環時，還需要注意一個問題：如果缺失的數值是數組的最大值（例如122，缺失3），此時需要單獨判斷，因為不存在一個數值使得后一個元素和當前元素差值為2，所以當數組的最后一個元素不等于數組的大小時，此時即為缺失數組最大值
- 異或運算
本題同樣可以考慮異或運算對重復數值和缺失數值分堆來求解，但是直接在原數組中對元素進行異或不可取
考慮到以下規律：
在原數組中，觀察到重復的數值和缺失的數值都出現偶數次，而其他數值均出現奇數次，如果構造一個1~n的不缺數的數組和原數組組合，那么重復的數值和缺失的數值都出現奇數次，而其他數值均出現偶數次，在異或運算中，相同的兩個數異或可以得到a^a = 0，而a^0 = a，故此時對構造的數組和原數組進行整體異或可以得到重復的數值和缺失的數值異或的結果值
故采用先構造一個數組和原數組進行整體異或，得到一個返回值ret即為重復數值和缺失數值的異或結果，因為異或運算的本質是找出兩個操作數二進制位不同的位置，所以計算結果的二進制位為1的位置即為重復的數值和缺失的數值相異的位置，此時可以采用循環結合右移運算符找到相異的位置（二進制位數的下標，例如1和5中倒數第三位不同），但是本次將采用返回值與返回值的負數形式相與計算得出最低的不同位，即int position = ret & (-ret);，但是注意該語句計算的不是不同的下標位置，而是具體的值，但是該值的二進制值中為1的位置為對應的兩個數不同的位置
找到最低的不同位之后，通過原數組和構造的數組中的元素與不同位的數值相與運算得到結果為0和不為0的數值，將二者分堆即可分出重復的數值和缺失的數值（因為重復的數值和缺失的數值不相同，所以二者不可能在同一堆中）
最后，因為暫時不知道重復的數值和缺失的數值具體所在的位置，所以需要遍歷原數組確定重復的數值存儲在新數組的第一個元素的位置，缺失的數值則放置到新數組的第二個位置
參考答案：
排序+調整（數學方法）
/** @lc app=leetcode.cn id=645 lang=c** [645] 錯誤的集合*/// @lc code=start
/*** Note: The returned array must be malloced, assume caller calls free().*/int cmp(const void *p1, const void *p2)
{return (*(int *)p1 - *(int *)p2);
}
int *findErrorNums(int *nums, int numsSize, int *returnSize)
{// 對已知數組進行從小到大排序qsort(nums, numsSize, sizeof(int), cmp);int *p = (int *)malloc(sizeof(int) * 2);// 定義變量記錄數組中上一個元素的位置，便于計算缺失的數值int prev = 0;// 遍歷數組// 1.如果找出的元素與prev中的值差值大于1，說明當前缺失的元素即為prev當前值的后一位數值// 2.如果找出的元素與prev中的值相等，說明遇到了相同元素for (int i = 0; i < numsSize; i++){int cur = nums[i]; // 遍歷數組if (cur == prev){// 如果相同則表示遇到相同元素p[0] = cur; // 記錄相同元素}else if (cur - prev > 1){// 如果不同且滿足二者差值大于1時，則表示中間有缺失元素，并且缺失元素即為prev當前大小+1p[1] = prev + 1;}prev = cur; // 更新prev}// 存在一種情況：數組中最后一個數值小于數組長度if (nums[numsSize - 1] != numsSize){// 數組中缺失的數值為數組的最大值p[1] = numsSize;}*returnSize = 2;return p;
}
// @lc code=end異或運算
/** @lc app=leetcode.cn id=645 lang=c** [645] 錯誤的集合*/// @lc code=start
/*** Note: The returned array must be malloced, assume caller calls free().*/int *findErrorNums(int *nums, int numsSize, int *returnSize)
{int *p = (int *)malloc(sizeof(int) * 2);int ret = 0;// 構造一個1-n的不缺數值的數組與原來的數組進行整體異或for (int i = 1; i <= numsSize; i++){// 將不缺數的數組進行整體異或ret ^= i;// 將缺數的數組與不缺數的數組進行整體異或ret ^= nums[i - 1];}// 當前ret中存儲的值為重復數值和缺失數值異或的結果// 找出重復數值和缺失數值二者最低的不同位// 可以代替原來的移位找最低不同位算法int position = ret & (-ret);// 定義兩個數值分別存儲重復數值和缺失的數值int num1 = 0;int num2 = 0;// 根據最低的不同二進制位對原數組進行分組for (int i = 0; i < numsSize; i++){if ((nums[i] & position) == 0){num1 ^= nums[i];}else{num2 ^= nums[i];}}// 根據最低的不同二進制位對構造數組進行分組for (int i = 1; i <= numsSize; i++){if ((i & position) == 0){num1 ^= i;}else{num2 ^= i;}}// 因為當前不確定重復的數值和缺失的數值在num1和還是num2，所以需要與原數組進行再一次的比較找出重復數值，剩下的就是缺失的數值*returnSize = 2;for (int i = 0; i < numsSize; i++){if (nums[i] == num1){p[0] = num1;p[1] = num2;return p;}}// 如果已經確定則直接返回p[0] = num2;p[1] = num1;return p;
}
// @lc code=end
