我是靠谱客的博主 神勇保温杯,这篇文章主要介绍一个整数数组里面,除了两个数之外,其他的数字都出现了两次,写一个程序找出这两个数,现在分享给大家,希望可以做个参考。

一个整数数组里面,除了两个数之外,其他的数字都出现了两次,写一个程序找出这两个数,要求算法的时间复杂度为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
4
for (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
11
for(i=0; i<length; i++) { if (testBit(date[i], pos)) { *num1 ^= date[i]; } else { *num2 ^= date[i]; } }

这里借助了异或的原理,pos位置上为1的其它成双成对的数肯定也是为1的,同理,pos位上为0的时也一样。

上面程序思路是我参考别人思路编写的代码,欢迎大家提出好的思路,一起学习一起进步!

最后

以上就是神勇保温杯最近收集整理的关于一个整数数组里面,除了两个数之外,其他的数字都出现了两次,写一个程序找出这两个数的全部内容,更多相关一个整数数组里面,除了两个数之外,其他内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(73)

评论列表共有 0 条评论

立即
投稿
返回
顶部