求缺省数字时可以使用异或停止求解，时间复杂度为O(N)。
我们都晓得，异或的特点就是相同为0，相异为1 ，比如：
这是3和3相异或的结果，为0， 同样地，有4^4 = 0,5^5 = 0等等……
这也是我们考虑这道题的动身点：
既然相同异或就为0，那么我们是不是只要将此数组与一个完好数组（个人习惯称为完全数组）挨个求异或，相同的数字就会被异或没，剩下的那个数字（这个数字是在完全数组中留下的）是不是就是题给数组的缺省数字？
答案是肯定的：
此时剩下的数字就是4即为所求。
但是我们怎么样用代码去实现呢？
实质上是两两求异或，非要两个数组的数字对应相异或吗？（1-1,2-2,3-3,5-5,6-6,7-7）
我们可以很快的实现一个完全数组的创建，找到缺省数组的最小值，往后加（N+1）个数便可得到，但是假设题给的数组是乱序呢？我们无法做到逐个对应去求异或。
于是，奇妙的异或运算便替我们省去了很多步骤。
异或运算是有交换律的，即：a⊕b = b⊕a;
难理解的话我们来看一个例子：
假设如今有一个数组：{1,2,1,3,4}；其中有两个 1 反复了，我已假设对这个数组停止两两异或结果是不是应该为2^3^4的值呢？
很显然，异或消去相同数并不需要对应，只要让这个数字最终和一个跟它相同的数字异或就可以消去；所以，我们可以将完全数组与缺省数组混合起来成为一个数组两两异或，就可以求出那个缺省数字。
思想就是这个样子，但是在实现时，假设要将两个数组合并为一个数组又得有多余的步骤，所以我的做法是将两个数组各自两两异或、得到结果A和结果B；再将A与B异或得到缺省数字。
拙解- #include <stdio.h>
- int fun(int arr[], int len);
- int main()
- {
- int arr[] = { 78, 79, 81, 83, 82, 84 };
- int len = sizeof(arr) / sizeof(arr[0]);
- int res = fun(arr, len);
- printf("%d\n", res);
- return 0;
- }
- int fun(int arr[], int len)
- {
- int i, j;
- int temp1 = 0, temp2 = 0;
- int min = arr[0];
- //确定完全数组起始值
- for (i = 0; i < len; i++)
- {
- if (arr[i] < min)
- {
- min = arr[i];
- }
- }
- //对完全数组停止异或
- for (j = min; j < (len + 1)+min; j++)
- {
- temp1 ^= j;
- }
- //对原始（缺数）数组停止异或
- for (i = 0; i < len; i++)
- {
- temp2 ^= arr[i];
- }
- int res = temp1 ^ temp2;
- return res;
- }
|
