在给定数组中找出只出现一次的数

83 阅读 0 评论 55 点赞

我是靠谱客的博主热情咖啡，最近开发中收集的这篇文章主要介绍在给定数组中找出只出现一次的数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题一

给定一个数组A[N]，其中有一个元素只出现一次，其他元素均出现偶数次，找出只出现一次的元素。其中元素的范围为[0, 263 −1]

方法一

算法基本思想：先遍历一边数组A[N]，获得最大值max，然后借助辅助数组sup[max],记录每一个元素出现的次数，，最后遍历辅助数组，找出只出现一次的元素即可。
代码实现：

// N为数组A[]的长度
unsigned long long search(unsigned long long A[],int N)
{
unsigned long long i,j,max = 0;
// 寻找最大值
for(i = 0; i < N;i++)
{
if(max < A[i])
max = A[i];
}
// 声明辅助数组并初始化
int sup[max];
for(i = 0; i< max; i++)
sup[i] = 0;
// 元素计数
for(i = 0; i < N, i++)
{
sup[A[i]] += 1;
}
// 遍历找出sup数组中值为1的下标，即为所求
for(i = 0;i < max; i++)
{
if(sup[A[i] == 1)
return A[i];
}
}

方法二

算法基本思想：偶数个相同的数进行异或所得结果为0，根据这一思想，遍历该数组，并进行异或，所得结果即为所要寻找的数

代码实现：

// N为数组长度
unsigned long long search(unsigned long long A[], int N)
{
int i,result=0;
for (i = 0; i < N; i++)
{
// 进行异或运算
result |= A[i];
}
// 返回结果
return result;
}

方法三

基本思想：一个数从二进制的角度来看，每位上不是0就是1，若是我们只从各个位来看，就把这一位的内容加起来，除以2，剩余的余数应该就是单独剩下的这个数在这一位上的值。然后把各位实际对应值相加即可得到只出现一次的数。
算法实现：

// N为数组的长度
unsigned long long search(unsigned long long A[], int N)
{
int i,j;
unsigned long long result;
// long long 数据类型所占位数
int length = sizeof（long long） * 8;
int bit_sum[length] = {0};
for(i = 0; i < length; i++)
{
// 求A[N]中每个元素对应i位数的值之和
for(j = 0; j< N;j++)
{
bit_sum[j] += (A[j] >> i) & 0x01;
}
// 只出现一次的元素对应第i位
bit_sum[j] = bit_sum[j]%2；
// 只出现一次的元素值
result |= bit_sum[j] << i;
}
return result;
}

方法四

算法基本思想：只用一个数来表示出现一次的位，也就是说这个数的为1的位就表示这个位上面的数出现过了一次，比如0x10001，就表示bit[0]和bit[4]就是出现过了一次的位。然后再用一个数表示出现过了两次的位，只要这个位出现过了2次，就把这个位拿清除掉，这样剩余的最后出现过一次的位的这个数就是我们要找的数了

代码实现：

// N为数组长度
unsigned long long search(unsigned long long A[], int N)
{
// 只出现一次位
unsigned long long ones = 0;
// 出现两次位
unsigned long long twos = 0;
int i;
for (i = 0; i < N; i++)
{
// 出现两次(注意次序)
twos = ones & A[i];
// 只出现一次
ones ^= A[i];
// 清除二次出现的位
ones &= ~twos;
}
return ones;
}

问题二

给定一个数组A[N]，其中有一个元素只出现一次，其他元素均出现奇数次，找出只出现一次的元素。其中元素的范围为[0, 263 −1]

问题一中的方法一可直接应用，方法二不能运用，方法三和四需要简单修改

方法三

基本思想： - 基本思想：一个数从二进制的角度来看，每位上不是0就是1，若是我们只从各个位来看，就把这一位的内容加起来，除以3，剩余的余数应该就是单独剩下的这个数在这一位上的值。然后把各位实际对应值相加即可得到只出现一次的数。
算法实现：
代码实现

// N为数组的长度
unsigned long long search(unsigned long long A[], int N)
{
int i,j;
unsigned long long result;
// long long 数据类型所占位数
int length = sizeof（long long） * 8;
int bit_sum[length] = {0};
for(i = 0; i < length; i++)
{
// 求A[N]中每个元素对应i位数的值之和
for(j = 0; j< N;j++)
{
bit_sum[j] += (A[j] >> i) & 0x01;
}
// 只出现一次的元素对应第i位
bit_sum[j] = bit_sum[j]%3；
// 只出现一次的元素值
result |= bit_sum[j] << i;
}
return result;
}

方法四

基本思想：

-只用一个数来表示出现一次的位，也就是说这个数的为1的位就表示这个位上面的数出现过了一次，比如0x10001，就表示bit[0]和bit[4]就是出现过了一次的位。然后再用一个数表示出现过了两次的位，再用一个数表示出现过了3次的位。只要这个位出现过了3次，就把这个位拿清除掉，这样剩余的最后出现过一次的位的这个数就是我们要找的数了。
代码实现：

unsigned long long search(unsigned long long A[], int N)
{
// 只出现一次位
unsigned long long ones = 0;
// 出现两次位
unsigned long long twos = 0;
// 出现三次
unsigned long long three = 0;
int i;
for (i = 0; i < N; i++)
{
// 出现两次(注意次序)
twos |= ones & A[i];
// 只出现一次
ones ^= A[i];
three = twos & ones;
// 清除三次出现的位
ones &= ~three;
twos &= ~three;
}
return ones;
}