前言：

今天在刷题的时候突然看到一道题，疑似一位故题。仔细一看，欸！这不是就是单身狗的升级版吗？我想那必须再安排一篇，不过由于本篇文章与上一篇单身狗文章所涉及的知识点基本相同，所以还请大家见谅！

我写的开心，大家也看个乐呵！不过还请单身的人不要介意，单纯觉得比较有意思，无意冒犯！毕竟连小编自己都是单身狗。

后续小编也会尽快更新完指针相关知识点！

一、题目：

在一场专为情侣们策划的盛宴中，竟然有两名单身者悄然混入。宴会的主人感到十分不悦，并寻求你的帮助，希望你能运用你敏锐的洞察力，协助她识破并找出这两名不合规矩的单身者。

（无意冒犯，只是提供一个题目的背景）

例如：

有数组的元素是：1，2，3，4，5，6，1，2，3，4，5，7

只有6和7只出现1次，要找出6和7.

二、代码展示（无注释的）

如果有想先自己思考的可以先看一看这个代码，后面也会有解析

<code>#include <stdio.h>

int find(int num) {

int index = 0;

while ((num & 1) == 0 && index < 32) {

num >>= 1;

index++;

}

return index;

}

void single(int arr[], int sz, int* n1, int* n2) {

int Re = 0;

for (int i = 0; i < sz; i++) {

Re ^= arr[i];

}

int index = find(Re);

*n1 = *n2 = 0;

for (int i = 0; i < sz; i++) {

if (((arr[i] >> index) & 1) == 1)

*n1 ^= arr[i];

else

*n2 ^= arr[i];

}

int main() {

int arr[] = {1,2,3,4,5,6,1,2,3,4,5,7};

int n1, n2;

int sz = sizeof(arr) / sizeof(arr[0]);

single(arr, sz, &n1, &n2);

printf("两只单身狗分别是：%d 和 %d\n", n1, n2);

return 0;

}

三、题解思路：

1.关于算法，我们依然使用的是异或运算，因为异或运算相同为0，所以将数组中所有的数字进行异或操作，最终得到的结果就是那两个只出现一次的数字的异或值。

例如：

举个例子： int arr[ ] = {1,1,2}

初始re = 0；

re = re ^ 1 = 1；此时re = 1；

re = re ^ 1 = 1 ^ 1 = 0;此时re = 0；

re = re ^ 2 = 0 ^ 2 = 2;此时re = 2；所以只出现一次的数字是2

2.找到这个异或结果中为 1 的某一位。根据异或运算不同为1，这一位为 1 说明在这一位上，那两个只出现一次的数字是不同的。

例如：数组{1,1,2}

异或运算：1^1^2 = 2;

0010   2的二进制

 异或的结果是0010，从右向左找1的位置

0000   0的二进制

0010   2的二进制

0000^0010 = 0010 (异或运算相同为0，不同为1)

我们可以发现0在这一位上的数字是0，2在这一位上的数字是2，说明结果为1的这一位，两个只出现一次的数字是不同的。

3.根据这一位将数组中的数字分为两组。一组是这一位为 1 的数字，另一组是这一位为 0 的数字。

再对这两组数字分别进行异或操作，就可以得到那两个只出现一次的数字。

例如，数组为{1,2,3,1,2,4}

第一步，将所有数字异或:1 ^ 2 ^ 3 ^ 1 ^ 2 ^ 4=7（二进制为0111 ）

第二步，找到异或结果中为 1 的一位，从右往左数第一位为 1 

第三步，根据这一位将数字分组：

这一位为 1 的数字:{3,4}这一位为 0 的数字:{1,2,1,2}

{1，2，3，1，2，4}异或过程

1 ^ 2 = 0001^0010 = 0011 = 3；

3 ^ 3 = 0011^0011 = 0000 = 0;

0 ^ 1 = 0000^0001 = 0001 = 1;

1 ^ 2 = 0001^0010 = 0011 = 3;

3 ^ 4 = 0011^0100 = 0111 = 7;

所以  1 ^ 2 ^ 3 ^ 1 ^ 2 ^ 4 = 7。

四、函数介绍

1.main函数

int main()

{

int arr[] = {1,2,3,4,5,6,1,2,3,4,5,7};

int n1, n2;

int sz = sizeof(arr) / sizeof(arr[0]);

single(arr, sz, &n1, &n2);

printf("两只单身狗分别是：%d 和 %d\n", n1, n2);

return 0;

}

 数组的输入：int arr[] = {1,2,3,4,5,6,1,2,3,4,5,7};数组元素个数计算： int sz = sizeof(arr) / sizeof(arr[0]);调用函数： single(arr, sz, &n1, &n2);

2.single函数

void single(int arr[], int sz, int* n1, int* n2) {

int Re = 0;

for (int i = 0; i < sz; i++) {

Re ^= arr[i];

}

int index = find(Re);

*n1 = *n2 = 0;

for (int i = 0; i < sz; i++) {

if (((arr[i] >> index) & 1) == 1) {

*n1 ^= arr[i];

}

else {

*n2 ^= arr[i];

}

}

}

single函数作用：找出数组中两个只出现一次的数字

第一个for循环实现数组中所有元素的异或运算

第二个for循环用于根据索引值，将数组分为两组并分别进行异或运算

 int index = find(Re);将索引值传给find函数

3.find函数

int find(int num) {

int index = 0;

while ((num & 1) == 0 && index < 32) {

num >>= 1;

index++;

}

return index;

}

 find函数用于找到一个数的二进制表示中从右往左第一个为 1 的位的索引

五：代码展示（含注释）

#include <stdio.h>

int find(int num)

int index = 0;

while ((num & 1) == 0 && index < 32) // 当前二进制位为 0 并且索引小于 32

{

num >>= 1;//实现二进制中每位检查

index++;

}

return index;// 返回第一个结果为 1 的位的索引

}

void single(int arr[], int sz, int* n1, int* n2)

int Re = 0;

// 对数组中所有数字进行异或操作，得到两个只出现一次数字的异或结果

for (int i = 0; i < sz; i++)

{

Re ^= arr[i];

}

int index = find(Re);// 找到上述异或结果中第一个为 1 的位的索引

*n1 = *n2 = 0;

// 根据找到的索引位，将数组数字分为两组并分别异或

for (int i = 0; i < sz; i++)

{

if (((arr[i] >> index) & 1) == 1) // 判断当前数字在指定索引位是否为 1

*n1 ^= arr[i];

else

*n2 ^= arr[i];

}

}

int main()

{

int arr[] = { 1, 2, 3, 2, 1, 4 };

int n1, n2;

int sz = sizeof(arr) / sizeof(arr[0]);//计算数组元素

single(arr, sz, &n1, &n2);//函数调用

printf("两只单身狗分别是：%d 和 %d\n", n1, n2);

return 0;

}