编号0026 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
题目示例如下
这里其实是一道我一个月之前做的题目
在学弟的博客里刚好看到了 又翻了翻自己的博客 好像没有这道题目的题解
刚看到第一眼还以为自己不会了 慢慢梳理了下思路
这里其实又很多种做法 排序之后对比前后数字啊
使用一个很大的数组将它们依次赋值给数组里面对应的值啦
当然这里最优的解法应该是异或法
我们想想看将整个数组里面所有的元素异或 是不是就能得到那两个不同数字的异或了
（因为相同的数字异或都变成0了）
那么首先 我们可以将整个数组异或下来得到一个数字
就像这样
//首先使用一个测试数字0 让他一一和数组里面的异或 //异或完毕之后就会只剩下两个数字的异或结果 int test = 0; int i = 0; for(i=0;i<numsSize;i++) { test^=nums[i]; }
之后得到这个结果了之后怎么办呢？
我们之后要将整个数组分成两个 尤其是这两个不同的数字要在不同的组别中
那么要怎么分呢？
这也是这个题目唯一的难点
我们可以利用 ‘位’ 来分组
我们都知道了 test是这两个数字异或的结果
那么说明了什么呢？
是不是这个数字的二进制中为1的位 一定是这两个数的位不同的
仔细思考下异或的性质
那么想明白这个事情之后就简单了
我们开始利用这个性质分组
首先找出不同的位在哪里（1）
// 之后我们可以将这个数组分成两个 （这其中两个数字要不在同一个地方） // 这两个数字异或结果为1的地方一定是不相等的 // 所以我们首先要找出第一个出现1的地方 // 我们使用count来计数这个1出现的地方 int count =0; for(i=0;i<32;i++) { if((test>>i)&1==1) { break; } count++; }
再之后分别异或下就可以了
// 之后我们用count将数组分组 分别异或两个数得到的就是两个数了 int num1 = test; int num2 = test; for(i=0;i<numsSize;i++) { if((nums[i]>>count)&1 == 1) { num1^=nums[i]; } else { num2^=nums[i]; } } //存放到动态数组里面 int* a = (int*)malloc(sizeof(int)*2); a[0]=num1; a[1]=num2; // 最后设定下返回数组的大小就可以 *returnSize = 2; return a; }
整体代码表示如下
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* singleNumbers(int* nums, int numsSize, int* returnSize) { //首先使用一个测试数字0 让他一一和数组里面的异或 //异或完毕之后就会只剩下两个数字的异或结果 int test = 0; int i = 0; for(i=0;i<numsSize;i++) { test^=nums[i]; } // 之后我们可以将这个数组分成两个 （这其中两个数字要不在同一个地方） // 这两个数字异或结果为1的地方一定是不相等的 // 所以我们首先要找出第一个出现1的地方 // 我们使用count来计数这个1出现的地方 int count =0; for(i=0;i<32;i++) { if((test>>i)&1==1) { break; } count++; } // 之后我们用count将数组分组 分别异或两个数得到的就是两个数了 int num1 = test; int num2 = test; for(i=0;i<numsSize;i++) { if((nums[i]>>count)&1 == 1) { num1^=nums[i]; } else { num2^=nums[i]; } } //存放到动态数组里面 int* a = (int*)malloc(sizeof(int)*2); a[0]=num1; a[1]=num2; // 最后设定下返回数组的大小就可以 *returnSize = 2; return a; }
总的来说还是很开心的！ 一个月前死活想不出来的题目现在看一眼有思路 十分钟就可以敲出来了
继续加油！
