解答
我们想到异或运算的一个性质：任何一个数字异或他自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每个数字，那么最终结果刚好是那个只出现一次的数字，那些出现两次以上的数字全部在异或中抵消了。
可这道题目是有两个只出现一次的数字。怎么拆成两个子数组呢？我们先遍历数组全部异或一遍，得到的结果就是那两个数字的异或结果，由于这两个数字不同，所以异或结果不为0，在二进制中至少有一位为1，那么我们就可以根据这一位是不是为1，把数字划分成两个子数组，然后就能求解了。而且相同的数不可能分别分配到两个子数组中，因为它们的二进制也是相同的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | #include<bits/stdc++.h>using namespace std;void findOnce(int* a, int len) { if (a == nullptr || len <= 0) return; int XOR = 0; for (int i = 0; i < len; i++) //求异或值 XOR ^= a[i]; int idx = 0; while ((XOR & 1) == 0) {//求最右的1 XOR >>= 1; idx++; } int n=0, m=0;//两个子数组分别异或 for (int i = 0; i < len; i++) { if (((a[i] >> idx) & 1) == 0) n ^= a[i]; else m ^= a[i]; } printf("%d %d", n, m);}int main() { int a[8] = { 2,4,3,4,6,3,5,2 }; findOnce(a, 8); return 0;}//运行结果：6 5 |
帖子还没人回复快来抢沙发