代码如何实现找出数组当中只出现一次的数字呢?具体的代码实现和思路是怎样的?下面一起来看看实例。
题目：
一个整型数组当中，除去2个数字以外，其它的数字都已经出现过了2次。
请写程序，将这2个只出现了一次数字找出来。
思路1：
可以使用位运算来实现。
假如将所有数字相异或，那么最后的结果肯定是那两个只出现一次的数字异或的结果，所以，依据异或的结果1所在的最低位，将数字分成2半，每一半里都还有只出现1次的数据和成对出现的数据，这样继续对每一半相异或那么就能够分别求出2个只出现了1次的数字了。
代码实现：
class Solution
{
public:
void FindNumsAppearOnce(vector < int > data, int * num1, int * num2)
{
if (data.size() < 2)
return;
int size = data.size();
int temp = data[0];
for (int i = 1; i < size; i++)
temp = temp ^ data[i];
if (temp == 0)
return;
int index = 0;
while ((temp & 1) == 0)
{
temp = temp >> 1;
++index;
}
* num1 = * num2 = 0;
for (int i = 0; i < size; i++)
{
if (IsBit(data[i], index))
*
num1 ^= data[i];
else
*num2 ^= data[i];
}
}
bool IsBit(int num, int index)
{
num = num >> index;
return (num & 1);
}
};思路2：
首先：位运算中异或的性质：
2个相同数字异或=0，一个数和0异或还是它本身。
当只有一个数出现1次的时候，将数组中所有的数，依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了。
按照这个思路：
看一看2个数(我们假设是AB)出现一次的数组。
首先还是先异或，剩下的数字肯定是A、B异或的结果，这个结果的二进制中的1，表现的是A和B的不同的位。
取第一个1所在的位数，假设是第3位，接着把原数组分成两组，分组标准是第3位是否为1。
如此，相同的数肯定在一个组，因为相同数字所有位都相同，而不同的数，肯定不在一组。
之后将这两个组按照最开始的思路，依次异或，剩余的2个结果就是这2个只出现1次的数字。
代码实现：
public class Solution
{
public void FindNumsAppearOnce(int[] array, int[] num1, int[] num2)
{
int length = array.length;
if (length == 2)
{
num1[0] = array[0];
num2[0] = array[1];
return;
}
int bitResult = 0;
for (int i = 0; i < length; ++i)
{
bitResult ^= array[i];
}
int index = findFirst1(bitResult);
for (int i = 0; i < length; ++i)
{
if (isBit1(array[i], index))
{
num1[0] ^= array[i];
}
else
{
num2[0] ^= array[i];
}
}
}
private int findFirst1(int bitResult)
{
int index = 0;
while (((bitResult & 1) == 0) && index < 32)
{
bitResult >>= 1;
index++;
}
return index;
}
private boolean isBit1(int target, int index)
{
return ((target >> index) & 1) == 1;
}
}思路3
代码实现：
/**
* 数组中有两个出现一次的数字，其他数字都出现两次，找出这两个数字
* @param array
* @param num1
* @param num2
*/
public static void findNumsAppearOnce(int[] array, int num1[], int num2[])
{
if (array == null || array.length <= 1)
{
num1[0] = num2[0] = 0;
return;
}
int len = array.length, index = 0, sum = 0;
for (int i = 0; i < len; i++)
{
sum ^= array[i];
}
for (index = 0; index < 32; index++)
{
if ((sum & (1 << index)) != 0) break;
}
for (int i = 0; i < len; i++)
{
if ((array[i] & (1 << index)) != 0)
{
num2[0] ^= array[i];
}
else
{
num1[0] ^= array[i];
}
}
}
/**
* 数组a中只有一个数出现一次，其他数都出现了2次，找出这个数字
* @param a
* @return
*/
public static int find1From2(int[] a)
{
int len = a.length, res = 0;
for (int i = 0; i < len; i++)
{
res = res ^ a[i];
}
return res;
}
/**
* 数组a中只有一个数出现一次，其他数字都出现了3次，找出这个数字
* @param a
* @return
*/
public static int find1From3(int[] a)
{
int[] bits = new int[32];
int len = a.length;
for (int i = 0; i < len; i++)
{
for (int j = 0; j < 32; j++)
{
bits[j] = bits[j] + ((a[i] >>> j) & 1);
}
}
int res = 0;
for (int i = 0; i < 32; i++)
{
if (bits[i] % 3 != 0)
{
res = res | (1 << i);
}
}
return res;
}这样的程序还是比较容易写的，大家都有自己的思路了吗?可以参考上面的实例去尝试着写一下。更多Java实例，请继续来本站了解吧。