从0备战蓝桥杯：找出只出现一次的数字，数单身狗

单个只出现一次的数字：

力扣链接：

136. 只出现一次的数字 - 力扣（LeetCode）

题目描述 ：

       给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]

输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]

输出：4

示例 3 ：

输入：nums = [1]

输出：1

思路分析：

如果不考虑时间复杂度和空间复杂度的限制，这道题有很多种解法，可能的解法有如下几种

• 使用集合存储数字：遍历数组中的每个数字，如果集合中没有该数字，则将该数字加入集合，如果集合中已经有该数字，则将该数字从集合中删除，最后剩下的数字就是只出现一次的数字。
• 使用哈希表存储每个数字和该数字出现的次数：遍历数组即可得到每个数字出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的数字。
• 使用集合存储数组中出现的所有数字，并计算数组中的元素之和：由于集合保证元素无重复，因此计算集合中的所有元素之和的两倍，即为每个元素出现两次的情况下的元素之和。由于数组中只有一个元素出现一次，其余元素都出现两次，因此用集合中的元素之和的两倍减去数组中的元素之和，剩下的数就是数组中只出现一次的数字。

那有没有什么简单又高效的算法呢？

位运算

对于这道题，可使用 异或运算 ⊕，异或运算有以下三个性质：

• 任何数和 0 做异或运算，结果仍然是原来的数
• 任何数和其自身做异或运算，结果是 0
• 异或运算满足交换律和结合律

我们举个例子进行说明，我们给定一个表达式，然后进行运算： 1⊕2⊕3⊕4⊕4⊕3⊕2⊕1

1. 对于串表达式使用交换律，他就等价于 1⊕1⊕2⊕2⊕3⊕3⊕4⊕4
2. 对其使用结合律就可以得到，（1⊕1）⊕（2⊕2）⊕（3⊕3）⊕（4⊕4）
3. 我们再对其使用第二条性质，就可以得到他的结果：0⊕0⊕0⊕0
4. 那么最后结果就是 0

那我们要是再在上述表达式末尾再加一个数呢？我们给定如下：1⊕2⊕3⊕4⊕4⊕3⊕2⊕1⊕7

1. 根据我们上述的推论，前 8 位数字亦或后的结果为 0
2. 也就是说表达式可以化简如下：0⊕7
3. 那我们再根据第一条性质，表达式最后的结果就是 7

   我们不妨再看看刚才的表达式，这不就是在一个大小为 9 的数组里面进行查找只出现一次的数字吗？那么到了这里思路就很清晰了，我们对整个数组进行异或运算，最后得出的结果就是我们要查找的 “只出现一次的数字”

完整代码：

因此，我们给出代码如下：

int singleNumber(int* nums, int numsSize)
{
  int single = 0;
  for (int i = 0; i < numsSize; i++)
  {
    single ^= *(nums + i);
  }
  return single;
}

我们也可以自己给出一个数组进行验证输出结果：

int main()
{
  int arr[] = { 5,3,2,2,3,4,5 };
  int single = 0;
  int sz = sizeof(arr) / sizeof(arr[0]);
  for (int i = 0; i < sz; i++)
  {
    //single = single ^ arr[i];
    single ^= arr[i];
  }
  printf("单身狗 是%d\n", single);
  return 0;
}

输出结果：

俩个只出现一次的数字：

思路分析：

       题目描述还是和上题一样，但是如果有俩个只出现一次的数字呢？倘若还是按照上述的解决方法处理，我们对整个数组进行异或运算后得到的值就相当于是对俩个单身狗进行异或运算的值，比如数组中有2个单身狗，一个是 5，一个是 7，他们的异或的结果是 2，就结果而言，这个值既不是 5，也不是 7，这个值没有任何意义，它什么都不是

       对此，我们又该如何解决呢？

       其实如果我们可以成功的将俩个整个数组分成俩组，每一组都只有一个只出现一次的数字，然后我们对这俩个数组分别使用第一道题目的方法就可以了，理论存在，那我们开始着手实现

       首先，怎么分，用什么分，怎么才能恰好的让俩个单独出现的数字分开，我们不妨想一想，可不可以利用刚才我们说到的那个没有意义的值，我们用二进制来思考思考

• 5 的二进制：0101
• 7 的二进制：0111
• 2 的二进制：0010

       我们可以发现，俩个数字之所以不同，是因为他们的二进制不同，而俩个单身狗也是如此，那我们只需要找到他们某一位的二进制是不同的，然后以这一位二进制作为判定标准，然后就可以将俩个单身狗分别放入俩个数组

因此我们设计思路如下：

1. 对整个数组进行异或，得到一个值（俩个单身狗异或的值）
2. 对整个数从右往左数，找到第一位不是 0 的数，并且记录下该数的位数 count
3. 对整个数组遍历判断，对整个数组往右右移 count 位，然后和 1 进行与运算，如果为结果为 1 就放进一个数组，如果为 0 就放进另一个数组
4. 然后对俩个数组分别进行异或操作，得到俩个单身狗

完整代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
  int arr[10] = { 1,2,3,4,5,1,2,3,4,6 };
  int arr1[10] = { 0 };
  int arr2[10] = { 0 };
  int diff = 0;
  int count = 0;
  int dog1 = 0;
  int dog2 = 0;
  //找到俩个单身狗的异或结果
  for (int i = 0; i < 10; i++)
  {
    diff ^= arr[i];
  }
  //找到需要判定的位数
  for (int i = 0; i < 32; i++)
  {
    if ((diff >> i) & 1)
    {
      count = i;
      break;
    }
  }
  int j = 0;
  int k = 0;
  //分组
  for (int i = 0; i < 10; i++)
  {
    if ((arr[i] >> count) & 1)
    {
      arr1[j++] = arr[i];
    }
    else
    {
      arr2[k++] = arr[i];
    }
  }
  //找出俩个单身狗
  for (int i = 0; i < 10; i++)
  {
    dog1^= arr1[i];
    dog2^= arr2[i];
  }
  printf("俩个单身狗分别是%d和%d", dog1, dog2);
  return 0;
}

输出结果：