【经典算法题】在数组中找两个单身狗-蒲公英云

【经典算法题】在数组中找两个单身狗

✨前言✨：

算法是一个程序员的内功，能很好的体现程序员的编程思维，通过学习和掌握常见的算法，不仅能提高coding能力，还能更加容易在笔面试中脱颖而出。本专栏将记录博主刷算法题的过程，不定期的会更新一些优质的算法题。如果对大家有帮助，别忘了三连支持哟！

✨前言✨：

✨题目描述✨

✨题目分析✨:

按位异或运算符

?一个单身狗?

?两个单身狗?

eor&（~eor+1）公式拿到二进制序列最右端的一个1

✨具体代码详解✨:

✨题目描述✨

?：

描述：

输入一个数组，数组中只有两个元素出现了一次，其它元素均出现了两次。

示例：

输入：1,4,5,8,9,2,1,5,9,4

输出：8 2

✨题目分析✨:

在解决这道题目之前我们首先来了解一下按位异或运算符的一些操作

按位异或运算符

1：首先按位异或是位运算符，操作的是二进制的比特位

2：其具体运算过程可以记为：相同为0，相异为1，当然也可以理解为无进位加法

3：a^a=0 a^0=a

任何一个数按异或上自己为0，按位异或上0等于它本身

4：按位异或运算支持交换律和结合律

?：现在我们了解了按位异或操作符，在解决这个问题前，我们先解决它的简化版本：一个数组中只有一个元素出现了一次，其它元素均出现了两次

?一个单身狗?

?这题的难点就在于我们是否能正确的理解按位异或运算的操作符，其实按位运算有一个功能：

如果我们把数组中的所有元素按位异或起来，利用交换律和结合律把所有相同的聚在一起，这时如果出现偶数次的元素就会消除掉，出现偶数次的就会保留下来，因此我们遍历一遍数组，将所有元素按位异或起来，得到的结果就是那个只出现一次的数字。

int num = 0;//把只出现一次的数字放在num中去
void FindAppearSingalNum(int arr[], int sz)
{
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        num ^= arr[i];
    }
}

?两个单身狗?

?：在解决完一个单身狗后我们知道，我们可以遍历一遍数组，将数组中的所有元素按位异或起来，这样就可以消除出现偶数次的元素。但是有一个问题：

因为数组中有两个元素出现一次，所以遍历一遍后eor=num1^num2;其中num1和num2是那个只出现一次的数字。

1：由于数组中有两个单身狗，所以num1!=num2,这就保证了eor！=0，所以在eor的二进制序列中一定会有一个1.

2：因为eor是由num1^num2的结果，所以在eor二进制中从右往左数第一个1处，num1和num2

在这一比特位上一定存在不同，那么我们利用分治法，将数组中这一比特位上是1的元素分成一组，将数组中这一比特位是0的元素分成一组，我们可以保证在每一组中都有唯一一个单身狗，这样把每一组按位异或起来，就能得到这两个单身狗。

?：现在这个问题就转化为了如何拿到eor中从右往左的第一个1

eor&（~eor+1）公式拿到二进制序列最右端的一个1

图解：

✨具体代码详解✨:

#include<stdio.h>
int num1 = 0;
int num2 = 0;
void FindAppearSingalNum(int arr[], int sz)
{
    //1:遍历一遍将所有数都按位异或起来
    int i = 0;
    int eor = 0;
    for (i = 0; i < sz; i++)
    {
        eor ^= arr[i];
    }
    //eor=num1^num2
    //2:取出eor最右端的1作为区分值
    int rightOne = eor & (~eor + 1);
    for (i = 0; i < sz; i++)
    {
        if (rightOne & arr[i])
        {
            num1 ^= arr[i];
        }
        else
        {
            num2 ^= arr[i];
        }
    }
}
int main()
{
    //测试用例
    int arr[] = { 1,4,5,8,9,2,1,5,9,4 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    FindAppearSingalNum(arr,sz);
    printf("这两个单身狗是:%d %d\n", num1, num2);
    return 0;
}