大家好，我是安然无虞。

每篇前言

博客主页：安然无虞

作者认证：2021年博客新星Top2

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请铁汁批评斧正。

火爆专栏：蓝桥杯基础算法剖析

欢迎加入：比特社区

面试题：数组中数字出现的次数

题目链接：数组中数字出现的次数
题目描述：
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例：

解题思路

首先，如果题目是这样的：一个数组nums里除某个数字之外，其他数字都出现了两次，请找出这个数字。
那么很简单，我们可以直接给出代码：

但是本题没有这么简单，方法还是那么个方法，不过需要我们多想一点。我们可以把数组分为两组进行异或，但是必须将这两个数分在不同的组里，而且相同的数字必须在同一组中，这样就可以知道是哪两个数字不同了。
但是难就难在，如何正确对这两个数字进行分组。
具体思路是这样的：

• 将数组中所有数进行异或， 保存异或结果；
• 找到异或结果中第一次出现1的位（任意出现1的位也可以）；
• 按照找到的这个位进行分组即可

OK，思路就是这么个思路，具体请看代码。

代码执行

int* singleNumbers(int* nums, int numsSize, int* returnSize)
{
	//思考：为什么这里我用的是calloc()，而不是malloc()?
   int* ret = (int*)calloc(2, sizeof(int));//注意，malloc()和calloc()的区别
   *returnSize = 2;
   int n = 0;//将n和数组中所有元素相异或，异或结果放到n中
   int i = 0;
   for(i = 0; i < numsSize; i++)
   {
       n ^= nums[i];
   }
   //找异或结果n中第一次出现1的位
   int count = 0;
   //注意运算符的优先级
   while((n & 1 << count) == 0)//异或：相同为0，相异为1
   {
       count++;
   }
   //按照第一次出现1的位置进行分组
   for(i = 0; i < numsSize; i++)
   {
       if(nums[i] & 1 << count)
           ret[0] ^= nums[i];
       else
           ret[1] ^= nums[i];
   }
   return ret;
}

   

  

   
1
   
2
   
3
   
4
   
5
   
6
   
7
   
8
   
9
   
10
   
11
   
12
   
13
   
14
   
15
   
16
   
17
   
18
   
19
   
20
   
21
   
22
   
23
   
24
   
25
   
26
   
27
   
28
  

完整代码：

三、遇见安然遇见你，不负代码不负卿。

码字不易，求个三连。

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/123785587