问题一
n个数中有一个数x出现了奇数次, 其他所有数均出现了偶数次, 要求通过O(n)时间复杂度的方法, 求x
解析, 通过异或操作, 每两个相同的数均会被成对消除, 剩下的就是出现奇数次的数
例如, $3$ $3$ $3$ $2$ $2$ $4$ $4$, 异或操作后结果为$3$
int a[n] = {.......}
int r = 0;
for(int i = 0 ; i < n; i++) {
r ^= a[i];
}
问题二
n个数中有两个数x, y出现了奇数次, 其他所有数均出现了偶数次, 找出x, y
解析, 通过异或操作, 得到一个结果值$A$, 对$A$的二进制位进行分解, 从而对原始数据进行分组异或
例如, $7$ $1$ $5$ $5$ $6$ $6$, 异或后相当于$7$ ^ $1 = 6$, 而$(6){10} = (110){2}$
其从右向左而言, 首个为$1$的位数是第二位
则$x、y$从右向左而言的第二位的值一定是一个为$1$且另一个为$0$, 这样它俩异或操作后值才为$1$
现可根据原数组中每个数字的右起第二位值将其分为两组
| 右起第二位为$0$ | 右起第二位为$1$ |
|---|---|
| $1(001) 、5(101) 、5(101)$ | $7(111) 、6(110) 、6(110)$ |
据此, 就转化为了第一问的问题
#include<stdio.h>
const int n = 6;
int main(void){
int a[n] = {7, 1, 5, 5, 6, 6}
int r = 0;
for(int i = 0; i < n; i++) {
r ^= a[i];
}
// 记录结果值右起第一个为1的位置
int t = 0;
for(int i = 0; r != 0; i++) {
if(r & 1){
t = i;
break;
}
r >>= 1;
}
int x = 0;
int y = 0;
for(int i = 0; i < n; i++) {
// 若a[i]的第t位为1
if(a[i] & (1 << t)) {
x ^= a[i];
}else{
y ^= a[i];
}
}
printf("%d, %d\n", x, y);
}
- python
n = 6
a = [7, 1, 5, 5, 6, 6]
r = 0
for i in range(n):
r ^= a[i]
t = 0
while(r):
if r & 1:
break
t += 1
r >>= 1
x, y = 0, 0
for i in range(n):
if a[i] & (1 << t):
x ^= a[i]
else:
y ^= a[i]
print(x, y)