找出数组中只出现一次的数字
问题描述：
一个整型数组里除了一个数字以外，其他数字都出现了两次。找出这个只出现一次的数字
算法思路：
* 异或运算：任何一个数字异或它本身都等于0,
* 如果从头到尾异或数组中的每一个数字，那些出现两次的数字全部在异或中会被抵消，
* 最终的结果刚好是这个只出现一次的数字
package JBArray;
/**
* 找出数组中只出现一次的数字
* @author Dan
*
*/
public class FindOnce {
/**
* 问题描述：
* 一个整型数组里除了一个数字以外，其他数字都出现了两次。找出这个只出现一次的数字
* 算法思路：
* 异或运算：任何一个数字异或它本身都等于0,
* 如果从头到尾异或数组中的每一个数字，那些出现两次的数字全部在异或中会被抵消，
* 最终的结果刚好是这个只出现一次的数字
* @param a
* @return
*/
public static int findNotDouble(int a[]){
int n = a.length;
int result = a[0];
int i;
for(i=1;i<n;++i){
result ^= a[i];
}
return result;
}
}
问题描述：
一个数组里除了一个数字之外，其他数字出现了n次，那么该如何找出这个数字呢？
1、先求出每一位出现1的个数
2、每一位个数整除n
优点：适用于奇数次或偶数次
代码实现：
/**
* 问题描述：一个数组里除了一个数字之外，其他数字出现了n次，那么该如何找出这个数字呢？
* @param a
* @param appearTimes
* @return
*/
public static int findOnce(int a[], int appearTimes){
int n = a.length;
int[] bitCount = new int[32];
//计算数组中所有数组对应的二进制数各个位置出现1的次数
for (int i = 0; i < n; i++) {
for (int j = 0; j < 32; j++) {
bitCount[j] += ((a[i]>>j)&1);
}
}
//若某位上的结果不能被整除，则肯定目标数字在这一位上
int appearOne = 0;
for (int i = 0; i < 32; i++) {
if (bitCount[i]%appearTimes != 0 ) {
appearOne += (1<<i);
}
}
return appearOne;
}
作者：hd_sky
来源：CSDN
原文：https://blog.csdn.net/hd12370/article/details/82343770
版权声明：本文为博主原创文章，转载请附上博文链接！
此题的扩展：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
分析：数组里包含了两个只出现一次的数字，那么所有数字依次异或的结果就是这两个只出现一次的数字的异或结果。我们要想办法利用这个异或结果，把数组分为两个子数组，一个子数组包含一个只出现一次的数字，另一个数组包含另一个只出现一次的数字。由于这两个只出现一次的数字肯定不相等，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1。我们在结果数字中找到第一个为1的位的位置，记为第N位。现在我们以第N位是不是1为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N位都为1，而第二个子数组的每个数字的第N位都为0。
举个栗子：1 2 3 4 2 3
所有数字异或结果 = 1 xor 4
二进制表示为： 001 xor 100 101
异或结果的二进制位101，第一个为1的位的位置N=1。
那么，数组所有数的二进制表示中，第N(N=1)位为1的的数为1 3 3，第N(N=1)位为0的的数为2 2 4.
这样就把原数组拆分为两个子数组，1和4被分到不同的数组中去了。然后分别在两个子数组中找只出现一次的那个数。
void FindNumsAppearOnce(int data[], int length, int &num1, int &num2)
{
if (length < 2)
return;
// get num1 ^ num2
int resultExclusiveOR = 0;
for (int i = 0; i < length; ++ i)
resultExclusiveOR ^= data[i];
// get index of the first bit, which is 1 in resultExclusiveOR
unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR);
num1 = num2 = 0;
for (int j = 0; j < length; ++ j)
{
// divide the numbers in data into two groups,
// the indexOf1 bit of numbers in the first group is 1,
// while in the second group is 0
if(IsBit1(data[j], indexOf1))
num1 ^= data[j];
else
num2 ^= data[j];
}
}
// Find the index of first bit which is 1 in num (assuming not 0)
unsigned int FindFirstBitIs1(int num)
{
int indexBit = 0;
while (((num & 1) == 0) && (indexBit < 32))
{
num = num >> 1;
++ indexBit;
}
return indexBit;
}
// Is the indexBit bit of num 1?
bool IsBit1(int num, unsigned int indexBit)
{
num = num >> indexBit;
return (num & 1);
}
