首页 > 代码库 > 数组中只出现一次的字符

数组中只出现一次的字符

2024-07-17 12:39:46   218人阅读

题目描述：
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
输入：
每个测试案例包括两行：
第一行包含一个整数n，表示数组大小。2<=n <= 10^6。
第二行包含n个整数，表示数组元素，元素均为int。
输出：
对应每个测试案例，输出数组中只出现一次的两个数。输出的数字从小到大的顺序。
样例输入：
8
2 4 3 6 3 2 5 5
样例输出：
4 6
思路：
设a、b仅出现一次。
1.假如数组中只有一个数字出现一次，其他数字均出现两次。我们可以通过异或的性质找到这个数字。因为异或有这样的性质，任何一个数异或自己总是0，0异或任何数都等于任何数本身。所以我们可以遍历数组，挨个异或，最后剩下的就是只出现一次的数字，其他数字都被抵消了。
2.现在我们的目的是将只出现一次的两个数分开，分别放到两个集合中，这样便可以利用1的结论来做。
3.我们仍然从头异或到尾，得到的结果为该数组中只出现一次的两个数字的异或值（a^b）,结果必然不是0，我们可以从右向左找到a^b中第一位为1的数(二进制)，表示a和b第一个不同的位，我们按照该位是否为1将数组分成两部分，那么每个部分均只有一个数字出现一次。

代码：

/*
数组中只出现一次的数字
by Rowandjj
2014/8/14
*/
#include<stdio.h>
#include<stdlib.h>
/**
 *找到数字xorVal的二进制中第一个值为1的位
 *
 */
int FirstBitIs1(int xorVal)
{
	int index = 0;
	while(((xorVal&1)==0) && (index < 8*sizeof(int)))//不能越界,注意运算符优先级，多加几个括号
	{
		index++;
		xorVal = xorVal>>1;
	}
	return index;
}
/**
 *判断data中第index位（二进制）是否为1
 */
bool isBit1(int data,int index)
{
	data = http://www.mamicode.com/data>>index;>
上面代码可以再优化下，有这样的一个性质：a&(-a)将会把a的二进制形式中最右边的1保留，其他位置0.比如10（1010）&-10（0110） = 0010。
代码：
/*
数组中只出现一次的数字
*/
#include<stdio.h>
#include<stdlib.h>
bool FindFirstAppearOnceNum(int data[],int len,int *num1,int *num2)
{
	if(data =http://www.mamicode.com/= NULL || len <= 1)>


联系
我们