问题
有一个 n 个元素的数组, 除了两个数只出现一次外, 其余元素都出现两次, 让你找出这两个只出现一次的数分别是几, 要求时间复杂度为 O(n) 且空间复杂度为 O(1)(与 n 无关).
例如:
输入: [1,2,2,1,3,4]
输出: [3,4]
解决方法
已知相同的两个数异或结果为 0, 在这里把所有元素都异或, 那么得到的结果就是那两个只出现一次的元素异或的结果.
然后, 因为这两个只出现一次的元素一定是不相同的, 所以这两个元素的二进制形式肯定至少有某一位是不同的, 即一个为 0 , 另一个为 1 , 现在需要找到这一位.
根据异或的性质 任何一个数字异或它自己都等于 0, 所以前面得到这个数字二进制形式中任意一个为 1 的位都是我们要找的那一位.
再然后, 以这一位是 1 还是 0 为标准, 将数组的 n 个元素分成两部分.
将这一位为 0 的所有元素做异或, 得出的数就是只出现一次的数中的一个
将这一位为 1 的所有元素做异或, 得出的数就是只出现一次的数中的另一个.
这样就解出题目. 忽略寻找不同位的过程, 总共遍历数组三次, 时间复杂度为 O(n)
代码:
- #include<cstdio>
- using namespace std;
- const int maxn = 100000 + 10;
- int num[maxn];
- int n;
- int main()
- {
- scanf("%d", &n);
- int res = 0; // 记录所有数的异或结果
- for (int i = 0; i < n; i++)
- {
- scanf("%d", &num[i]);
- res ^= num[i];
- }
- int pos; // 记录 "1" 的位置
- for(int i = 0;(1 << i) <= res;i++)
- if (res & (1 << i)) { pos = i; break; }
- int ans1 = 0, ans2 = 0; // 记录两个结果
- for (int i = 0; i < n; i++)
- {
- if (num[i] & (1 << pos)) ans1 ^= num[i];
- else ans2 ^= num[i];
- }
- printf("%d %d\n", ans1, ans2);
- return 0;
- }
参考链接:
- ,https://www.zhihu.com/question/269288074/answer/574871689
- ,https://www.cnblogs.com/hezhiyao/p/7539024.html
来源: http://www.bubuko.com/infodetail-2965697.html