一个整型数组里除了两个数字之外,其他的数字都出现了两次
本题和前面一个题型《一个整形数组里除了一个数字其他的所有值都是成对的》一样。在这里还是需要通过异或的方式解决。
因为异或是相同为0,不同为1,异或是基于位运算的。所以在这个题中,相同的所有的数异或后依然为0, 最后异或的结果就是两个不同的数异或的结果,因为他们不同,所以按位异或后32bit里面肯定或有一位是1,而我们就找这其中一位异或结果是1的那个位为基准。将数组分成两个数组,那么分下来后两个不同的数肯定就分在两个数组中。
上面说了这么多是不是有些不明白?其实我第一次看见这个的时候也不明白,我用一个例子说话吧。
1.a[] = {3,2,9,4,5,6,7,2,4,5,6,7};在这个数组中不同的两个数是9和3,这个数组通过异或运行后,其实就化成了9和3两个数的异或运算。
2. 运算如下:
从上面结果可知异或结果为10; 其中在他们位中第1,3位结果为1;我们可以以其中任意一个位为基准进行数组分类。我们按最低位的第1位来作为我们的基准。分出来的两个数组为第一组:{3,2,6,7,2,6,7}; 第二组{9,4,5,4,5};
3.知道为什么这么分组了吗?,就是因为他们异或不相同,那么肯定有一位是不一样的,一个数的那位肯定为1, 另一个数肯定为0,最后转换为我们之前说的那个一个数组中找只有一个数是单数的问题了。
4.对上面分出来的数据进行两次异或运算即可找到两个数了。
代码如下:数组
int FindNumsAppearOnce(int a[], int len)
{
int mOnceVal = 0;
if (len > 0)
{
for (int i = 0; i < len; i++)
{
mOnceVal ^= a[i];
}
}
return mOnceVal;
}
int gVal[2] = { 0 };
int* FindNumsApperaTwo(int a[], int len)
{
int mVal = 0;
int i = 0;
int mStandard = 0;
memset(gVal, 0x0, sizeof(gVal));
if (len > 0)
{
for (i = 0; i < len; i++)
{
mVal ^= a[i];
}
for (i = 0; i < 32; i++)
{
if (((mVal >> i) & 1) == 1)
{
mStandard = i;
break;
}
}
for (i = 0; i < len; i++)
{
if (a[i] & (1 << mStandard))
{
gVal[0] ^= a[i];//这里可以节约空间。
}
else
{
gVal[1] ^= a[i];
}
}
}
return gVal;
}
int main(int argc, char *argv[])
{
//Tree* tree = Tree_Create();
//Tree_Destroy(tree);
int a[] = { 10,2,3,4,5,6,7,6,7,5,4,3,2,33,22,44,33,22,10 };
int len = sizeof(a) / sizeof(&a[0]);
int val = FindNumsAppearOnce(a, len);
printf("val: %d\n", val);
int a1[] = { 10,2,3,4,5,6,7,6,7,5,4,3,2,33,22,44,33,22,10, 87 };
int len1 = sizeof(a1) / sizeof(&a1[0]);
int* mTwo = FindNumsApperaTwo(a1, len1);
printf("val1 = %d val2 = %d\n", mTwo[0], mTwo[1]);
int mTwo2[] = { 3,2,9,4,5,6,7,2,4,5,6,7};
len1 = sizeof(mTwo2) / sizeof(&mTwo2[0]);
mTwo = FindNumsApperaTwo(mTwo2, len1);
printf("mTwo2 = %d mTwo2 = %d\n", mTwo[0], mTwo[1]);
}
结果如下: