每日一题： 数组中数字出现的次数
链接: 数组中数字出现的次数
该题是“消失的数字”的进阶版，还没接触的读者可以先看这个：
链接：消失的数字
思路： 我们依然使用异或的方法，只不过这道题需要查找的是两个数字，所以我们得先找到这两个数字的异或数字：
首先将数组nums中的数字异或一遍，得到的就是只出现一次的数字的那两个数字的异或数字。
又因为该题要求要将returnSize改成只出现一次的数字，这里比较简单，就是两个嘛。
int* singleNumbers(int* nums, int numsSize, int* returnSize){
*returnSize = 2;
int *arr=(int*)malloc(sizeof(int)*2);
int n = 0;
for(int i = 0; i < numsSize; i++)
{
n ^= nums[i];
}
//后续。。。
}现在我们得到了n，那接下来怎么知道n是由哪两个数字组成的呢？ 以题目中的例一为例子，现在n的值是7（0111）：
并且我们发现个规律，就是如果n中某一位是1，那肯定是这两个数字之间，其中一个这一位为1，其中一个这一位为0，才能让n的这一位等于1。 所以我们想到一个方法找到这两个数字：
在 n 的二进制位中从右到左，找到第一位为1的位数，然后记下这个位为 j，接着把 nums 中的所有数依次判断，若在 j 位为1则放到一个数组中，为0则放到另一个数组中。最后再对这两个数组分别异或，就能求出这两个数字啦！
以这里例一为例，我们上面求出n等于0111，那么第一位为1的就刚刚好是第一位，然后把nums数组中第一位为1的放到一个数组，为0的放到另一个数组中去。
int j = 0;//用来存放第一个为1的位数
while(n > 0)
{
if(((n>>j) & 1) != 1)
{
j++;
}
else
{
break;
}
}
int arr0[10000] = {0};
int n0 = 0;
int arr1[10000] = {0};
int n1 = 0;
for(int i = 0; i < numsSize; i++)
{
if(((nums[i]>>j) & 1) == 0)
{
arr0[n0] = nums[i];
n0++;
}
else
{
arr1[n1] = nums[i];
n1++;
}
} 最后就是在两个数组中各自求出这两个数字啦，因为这两个数字已经被分离到了两个数组中去了。
int tmp0 = 0;
int tmp1 = 0;
for(int i = 0; i < n0; i++)
{
tmp0 ^= arr0[i];
}
for(int i = 0; i < n1; i++)
{
tmp1 ^= arr1[i];
}
arr[0] = tmp0;
arr[1] = tmp1;
return arr;
通过啦！ 完整的代码：
int* singleNumbers(int* nums, int numsSize, int* returnSize){
*returnSize = 2;
int *arr=(int*)malloc(sizeof(int)*2);
int n = 0;
for(int i = 0; i < numsSize; i++)
{
n ^= nums[i];
}
int j = 0;//用来存放第一个为1的位数
while(n > 0)
{
if(((n>>j) & 1) != 1)
{
j++;
}
else
{
break;
}
}
int arr0[10000] = {0};
int n0 = 0;
int arr1[10000] = {0};
int n1 = 0;
for(int i = 0; i < numsSize; i++)
{
if(((nums[i]>>j) & 1) == 0)
{
arr0[n0] = nums[i];
n0++;
}
else
{
arr1[n1] = nums[i];
n1++;
}
}
int tmp0 = 0;
int tmp1 = 0;
for(int i = 0; i < n0; i++)
{
tmp0 ^= arr0[i];
}
for(int i = 0; i < n1; i++)
{
tmp1 ^= arr1[i];
}
arr[0] = tmp0;
arr[1] = tmp1;
return arr;
}学到了不要忘记点赞哦！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-06-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
