一个整数数组里面，除了两个数之外，其他的数字都出现了两次，写一个程序找出这两个数

一个整数数组里面，除了两个数之外，其他的数字都出现了两次，写一个程序找出这两个数，要求算法的时间复杂度为O(n).

n为数组的长度。

程序代码如下：

//取二进制中首个为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、首先第一次遍历整个数组，找出不同的那两个数的异或后的结果,见下面这段代码.

for (i=0; i<length; i++)
{
ansXor ^= date[i];
//异或
}

2、找到异或结果中ansXor中用移位的方式找到第一个二进制数中为1的位置，这个很关键，找到这个位置后，说明在该位置上，这两个不同的数中，一个为0，一个为1，这个应该可以理解对吧？

//取二进制中首个为1的位置
int findFirstOne(int value)
{
int pos = 0;
while ((value&1) != 1)
{
value = value>>1;
pos++;
}
return pos;
}

for(i=0; i<length; i++)
{
if (testBit(date[i], pos))
{
*num1 ^= date[i];
}
else
{
*num2 ^= date[i];
}
}

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

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

最后

以上就是独特河马为你收集整理的一个整数数组里面，除了两个数之外，其他的数字都出现了两次，写一个程序找出这两个数的全部内容，希望文章能够帮你解决一个整数数组里面，除了两个数之外，其他的数字都出现了两次，写一个程序找出这两个数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。