2n+1个数中,n个数出现两次,找出只出现一次的数

背景

算法题目中很多经典的题型使用到的是二进制的位运算,对于与、或、非、异或等都有一些经典的题,下面介绍一道关于异或的经典题和它的相关变形。

题目

在一个长度为2n+1的数组中,n个数出现两次,只有一个数出现一次,找出这个只出现一次的数x.

示例:
假设输入的为 [1, 2, 3, 4, 3, 2, 1],其中1,2,3都出现了两次,只有4出现一次,因此算法输出为4.

基本解法

最容易想到的解法便是对数组进行两层循环遍历,这种算法的平均时间复杂度为$O(n^2)$

代码如下

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
public class Main {
public static void main(String[] args) {
int a[] = {1, 2, 3, 4, 3, 2, 1, 5, 5};
for(int i=0; i<a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println("\nres: "+findNumber(a, a.length));
}
public static int findNumber(int[] a, int n) {
int x = 0;
boolean flag;
for(int i=0; i<n; i++) {
x = a[i];
flag = true;
for(int j=0; j<n; j++) {
if(a[j] == x && j != i)
flag = false;
}
if(flag)
return x;
}
return x;
}
}

输出为:

1 2 3 4 3 2 1 5 5
res: 4

位异或解法

位异或的解法使用到的思想主要有两个

  1. 相同的两个数异或结果为0, 如 3 ^ 3 = 0
  2. 异或满足交换律,也就是 A ^ B ^ C ^ A = A ^ A ^ B ^ C = B ^ C

算法: 将数组依次进行疑惑,其结果就是只出现了一次的数x

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Main1 {
public static void main(String[] args) {
int a[] = {1, 2, 3, 4, 3, 2, 1, 5, 5};
for(int i=0; i<a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println("\nres: "+findNumber(a, a.length));
}
public static int findNumber(int[] a, int n) {
int x = 0;
for(int i=0; i<n; i++)
x ^= a[i];
return x;
}
}

输出为:

1 2 3 4 3 2 1 5 5
res: 4

题目变形1

在一个长度为2n+2的数组中,n个数出现两次,有两个数出现一次,找出这两个只出现一次的数x, y.

算法的解决思想

  1. 仍然使用位异或的算法,将数组依次进行异或操作,得到 res = x ^ y
  2. 找到res从低位数第一个出现1的位置i,得到 $pivot = 2^i$(2的i次方).
    如 res = 1001000(2进制数), 则 pivot = 1000(2进制)= 8 = $2^3$
    • 解释: 因为第一个出现1的位置相当于说是 x 和 y 第一个不同的位置,也就是x和y在该位置要么x为0,y为1;要么x为1,y为零。从第i位往下数,x和y的值相同
  3. 将数组每个数字a[i]和 pivot进行与运算,如果为零, 则 res_1 ^= a[i];
    否则, res_2 ^= a[i], 则 res_1 为 x, res_2 为 y.
    • 解释: 将 a[i] & pivot 本质上将数组中的数分为了两类:一类结果为0,一类结果为1。而x,y必定被分在两个不同的类中,因为x,y在第i位不同,且$pivot=2^i$,也就是说pivot除第i位外,其余位均为0,因此x,y和pivot的与必定一个为0,一个为1。最终res_1 = a[i] ^ x; res_2 = a[i] ^ y; a[i]中相同的两个数异或后相互抵消,所以 res_1 = x; res_2 = y;

代码如下

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
28
29
30
31
32
33
34
35
36
37
38
public class Main1 {
public static void main(String[] args) {
int a[] = {1, 2, 3, 4, 3, 2, 1, 5, 5, 20};
for(int i=0; i<a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.print("\nres: ");
int[] res = findTwoNumber(a, a.length);
for(int i=0; i<res.length; i++)
System.out.print(res[i]+" ");
}
public static int[] findTwoNumber(int[] a, int n) {
int res = 0;
for(int i=0; i<n; i++)
res ^= a[i];
int index = 0;
while ((res & 1) ==0) {
res = res >> 1;
index++;
}
int pivot = 1 << index;
int[] arr = {0, 0};
for(int i=0; i<n; i++) {
if((a[i] & pivot) == 0)
arr[0] ^= a[i];
else
arr[1] ^= a[i];
}
return arr;
}
}

输出为:

1 2 3 4 3 2 1 5 5 20
res: 4 20

题目变形2

在一个长度为3n+1的数组中,n个数出现3次,只有一个数出现一次,找出这个只出现一次的数x.

算法思想

如果数组中没有x,那么数组中所有的数字都出现了3次,在二进制上,每位上1的个数肯定也能被3整除。如{1, 5, 1, 5, 1, 5}从二进制上看有:

1:0001

5:0101

1:0001

5:0101

1:0001

5:0101

二进制第0位上有6个1,第2位上有3个1.第1位和第3位上都是0个1,每一位上的统计结果都可以被3整除。而再对该数组添加任何一个数,如果这个数在二进制的某位上为1都将导致该位上1的个数不能被3整除。因此通过统计二进制上每位1的个数就可以推断出x在该位置上是0还是1了,这样就能计算出x了。

推广一下,所有其他数字出现m(m>=2)次,而一个数字出现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
28
import java.util.Arrays;
public class Main2 {
public static void main(String[] args) {
int a[] = {1, 2, 2, 1, 3, 3, 4, 5, 3, 2, 1, 5, 5, 4, 4, 10};
for(int i=0; i<a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println("\nres: "+findNumber(a, a.length));
}
public static int findNumber(int[] a, int n) {
int bits[] = new int[32];
Arrays.fill(bits,0);
for(int i=0; i<n; i++)
for(int j=0; j<32; j++) {
bits[j] += ((a[i] >> j) & 1);
}
int res = 0;
for(int j=0; j<32; j++)
if(bits[j] % 3 != 0)
res += (1 << j);
return res;
}
}

输出为:

1 2 2 1 3 3 4 5 3 2 1 5 5 4 4 10
res: 10

总结

无论是2n+1,还是3n+1,其实都是所有其他数字出现m次,而一个数出现1次。这种情况之下,都可以使用3n+1 的算法的核心思想,也就是统计每个二进制位上的1的个数,然后对2求余或者对3求余(异或其实就是一种对2求余的快捷方式)。只要掌握了这种核心思想,不管是几n+1, 都可以在 O(n)的时间复杂度中求出。