一个整数数组里面,除了两个数之外,其他的数字都出现了两次,写一个程序找出这两个数,要求算法的时间复杂度为O(n).
n为数组的长度。
程序代码如下:
复制代码
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52//取二进制中首个为1的位置 int findFirstOne(int value) { int pos = 0; while ((value&1) != 1) { value = value>>1; pos++; } return pos; } //测试某位置是否为1 char testBit(int value, int pos) { return ((value>>pos)&1); } int findNums(int date[], int length, int *num1, int *num2) { if (length < 2) { return -1; } int ansXor=0; int i = 0; int pos = 0; for (i=0; i<length; i++) { ansXor ^= date[i]; //异或 } pos = findFirstOne(ansXor); *num1 = *num2 = 0; for(i=0; i<length; i++) { if (testBit(date[i], pos)) { *num1 ^= date[i]; } else { *num2 ^= date[i]; } } return 0; }
1、首先第一次遍历整个数组,找出不同的那两个数的异或后的结果,见下面这段代码.
复制代码
1
2
3
4for (i=0; i<length; i++) { ansXor ^= date[i]; //异或 }
2、找到异或结果中ansXor中用移位的方式找到第一个二进制数中为1的位置,这个很关键,找到这个位置后,说明在该位置上,这两个不同的数中,一个为0,一个为1,这个应该可以理解对吧?
复制代码
1
2
3
4
5
6
7
8
9
10
11//取二进制中首个为1的位置 int findFirstOne(int value) { int pos = 0; while ((value&1) != 1) { value = value>>1; pos++; } return pos; }
我们把这个位置记为pos
3、然后再遍历一次数组,把这个数组分成两个子数组,pos位上为1的,和pos位上为0的
复制代码
1
2
3
4
5
6
7
8
9
10
11for(i=0; i<length; i++) { if (testBit(date[i], pos)) { *num1 ^= date[i]; } else { *num2 ^= date[i]; } }
这里借助了异或的原理,pos位置上为1的其它成双成对的数肯定也是为1的,同理,pos位上为0的时也一样。
上面程序思路是我参考别人思路编写的代码,欢迎大家提出好的思路,一起学习一起进步!
最后
以上就是神勇保温杯最近收集整理的关于一个整数数组里面,除了两个数之外,其他的数字都出现了两次,写一个程序找出这两个数的全部内容,更多相关一个整数数组里面,除了两个数之外,其他内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复