题目：找到所有数组中消失的数字

给定一个范围在1 ≤ a[i] ≤ n (n = 数组大小 ) 的整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例:

输入:
[4,3,2,7,8,2,3,1]

输出:
[5,6]

来源：力扣（LeetCode）第448题

链接：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array

分析：

有多种方法，第一种是用抽屉原理和异或运算的方式交换值。第二种是一种更为巧妙的方式。

使用异或运算交换两个值的方法：

a = a ^ b
b = a ^ b
a = a ^ b
这样就可以在不使用第三个变量的前提下交换两个变量的值。

抽屉原理：

如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有 n + 1 个元素放到 n 个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。

思路：

第一种：
- 遍历整个数组，从第一个开始i，不停地把这个位置上的元素i与它的值所对应的下标位置上的元素进行交换。
- 一旦当前遍历的这个位置上的元素i与它值所对应的下标位置上的元素相等，那么就遍历数组的下一个元素i。
- 这样的目的是，要么当前位置上i存的是正确的位置，比如i = 0的位置上存的是1，因为数组中的元素是从1开始的；要么当前位置i上存的是出现了两次的元素。
- 这样最后判断每个元素的值是否是其下标+1。
第二种：
- 遍历整个数组，将该元素的值所对应的下标位置的值变为负数。
- 遍历完后，如果数组中还有位置上的值是正数，那么说明没有值等于该位置的下标，即数组中没有遍历到这个值。

两种方法的代码：

第一种：

class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
    for i in range(len(nums)):
        while nums[i] != nums[nums[i] - 1]:  # 一直交换，直到值正确或者这个值出现了两次。
            tmp = nums[i] - 1  # 临时储存，如果用函数可以不写这个。
            if i == tmp:  # 如果两个值相等不能用异或交换，否则一个值会为0
                break
            nums[i] = nums[i] ^ nums[tmp]  # 异或交换
            nums[tmp] = nums[i] ^ nums[tmp]
            nums[i] = nums[i] ^ nums[tmp]
    return [i+1 for i in range(len(nums)) if i+1 != nums[i]]  # 返回正确位置的值

第二种：

class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
    for i in range(len(nums)):
        nums[abs(nums[i]) - 1] = -abs(nums[abs(nums[i]) - 1])  # 把当前值所对应的下标上的值变为负数，需要注意的是可能这个值已经是负数了，比如有的值出现了两次，所以要加绝对值。
    return [i + 1 for i in range(len(nums)) if nums[i] > 0]  # 把大于0的数返回

复杂度分析：

时间复杂度：O(n)
空间复杂度：O(1)