A. 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

思路分析:

解析来自 https://www.cnblogs.com/Kobe10/p/6306183.html 

首先我们考虑这个问题的一个简单版本：一个数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。

这个题目的突破口在哪里？题目为什么要强调有一个数字出现一次，其他的出现两次？我们想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现依次的数字，因为那些出现两次的数字全部在异或中抵消掉了。

有了上面简单问题的解决方案之后，我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中，包含一个只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照前面的办法就是分别求出这两个只出现一次的数字了。

我们还是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次，在异或中全部抵消掉了。由于这两个数字肯定不一样，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1。我们在结果数字中找到第一个为1的位的位置，记为第N位。现在我们以第N位是不是1为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N位都为1，而第二个子数组的每个数字的第N位都为0。现在我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。因此到此为止，所有的问题我们都已经解决。

代码实现待补充

 

 B. 在一个长度为n的数组里的所有数字都在0-n-1的范围内，数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次 。请找出数组中任意一个重复的数字。要求O(n)的时间复杂度和O(1)的空间复杂度

思路分析：

解析来自：https://www.cnblogs.com/ourener/p/9736935.html

1、因为总共有N个数，每个数的范围是1到N-1，只有一个重复的数，所以这些数肯定是连续的；

2、我们的想法是，从数组中取一个数，将它放到数组中与之对应的下标位置上去，但是这样有可能会覆盖掉原来在该位置上的数字；

3、因此可以申请一个临时变量tmp, 来先保存将要被覆盖位置上的数字，然后将取出的数放到数组中与之对应的下标位置上去；

4、对tmp中保存的数重复2~3步的操作。如此循环操作，当arr[0]上的数字与对应位置上的数字相等时，就找到了重复的元素

5、最坏的情况下循环N次一定能找出来重复的元素

由于只申请了一个临时变量tmp，所以空间复杂度为O(1); 时间复杂度为O(n)

代码实现待补充

C.给你1-1000个连续自然数，然后从中随机去掉两个，再打乱顺序，要求只遍历一次，求出被去掉的两个数。

思路分析：

解法1：使用异或。https://www.cnblogs.com/Kobe10/p/6306183.html

说说异或的两个特性：顺序无关 / 对一个数异或两次等于没有异或。顺序无关就是说异或的元素可以随意交换顺序，而不会影响结果。异或两次可以理解为+x和-x。

本题，将包含数字1~1000数组A和去掉两个数数字打乱顺序的数组B两个数组合并，就是一个和问题A的输入一样的条件：一个数组其他数字都有两个，只有两个数字只有一个，找出他们。