目录
2.出现一次的两个数字：只有两个数字出现1次，其余都出现两次
3.数组中出现了一次的数字：其他数字出现了k次，一个数出现一次
1.出现1次的数：其他数字只出现了2次
异或运算：二进制位的每一位相同为0,不同为1
#include<stdio.h>
int Search(int* p, int sz)
{
int s = 0;//0和任何数&都是任何数
for (int i = 0; i < sz; i++)
{
s ^= *(p + i);//出现了两次的数字&结果是0
}
return s;
}
int main()
{
int arr[9] = { -1,-2,-3,-4,-2,-3,-4,1,1 };
printf("%d", Search(arr, 9));
return 0;
}2.出现一次的两个数字：只有两个数字出现1次，其余都出现两次
?方法1：异或
#include<stdio.h>
int x = 0, y = 0;
int Search(int* p, int sz)
{
int s = 0; int m = 0;
for (int i = 0; i < sz; ++i)
{
s ^= *(p + i);//最后的结果是两个出现了一次的数字相异或
}
while (m < 32)
{
if ((s >> m) & 1)//找出s里面二进制位是1的某一位
break;
else
++m;
}
for (int i = 0; i < sz; i++)//按照第m位是否是1，将数组元素分为两部分
{
if ((p[i] >> m) & 1)
x ^= p[i];
else
y ^= p[i];
}
}
int main()
{
int arr[10] = { 1,2,-1,-2,1,2,-1,-2,9,8 };
Search(arr, 10);
printf("%d %d", x, y);
return 0;
}方法2： 排序
#include<stdio.h>
int x = 0, y = 0;
void sort(int* p, int sz)
{
for (int i = 0; i < sz-1; i++)
{
for (int j = 0; j < sz - 1 - i; j++)
{
if (*(p + j) < *(p + j + 1))
{
int tmp = p[j];
p[j] = p[j + 1];
p[j + 1] = tmp;
}
}
}
}
int Search(int* p, int sz)
{
for (int i = 0; i < sz ; i++)
{
if ((p[i] != p[i - 1]) && (p[i] != p[i + 1]))
printf("%d ", p[i]);
}
}
int main()
{
int arr[10] = { 1,2,-1,-2,1,2,-1,-2,0,8 };
sort(arr, 10);
Search(arr, 10);
return 0;
}3.数组中出现了一次的数字：其他数字出现了k次，一个数出现一次
?思路：由于一个数出现了奇数次，所以说使用异或运算就是错误的。
一个数出现了三次，那么它的二进制位就出现了三次，我们将所有的二进制位的每一位累加求和，得到的数字看是不是三的倍数，如果不是，那么所求数x的这一位必定是1，是那么就是0
?0101 ?0101? 0101? 0111? ? ? ? ? b[0]=4,b[1]=1,b[2]=4? ? 根据b[i]%k!=0 所以x=0111
#include<stdio.h>
int foundOnceNumber(int* arr, int arrLen, int k) {
int b[32] = { 0 };
for (int j = 0; j < 32; j++)
{
int sum = 0;
for (int i = 0; i < arrLen; i++)
{
sum += ((arr[i] >> j) & 1);
}
b[j] = sum;
}
//b数组里面存放的是每一个数字的二进制的每一位数字之和
int ans = 0;
for (int i = 0; i < 32; i++)
{
if (b[i] % k != 0)
ans += (unsigned int)1<<i;
}
return ans;
//当数字不是k的倍数时，得到的就是x二进制中为一的那位，左移还原
//1是int类型，当1<<31时，得到的是10000000 00000000 00000000 00000000，
//对应 补码是1 00000000 00000000 00000000 00000000，超过了int的范围（2^31-1~-2^31),
//所以说强制转换称为无符号类型
}
int main()
{
int arr[10] = { -2,-2,1,1,4,1,4,4,-4,-2 };
printf("%d", foundOnceNumber(arr, sizeof(arr), 3));
//k表示有多少个数字相同，这里k=3
}