栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > C/C++/C#

leetcode260.只出现一次的数字III

C/C++/C# 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

leetcode260.只出现一次的数字III

题目简介:

给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

示例 1:

输入:nums = [1,2,1,3,2,5]
输出:[3,5]
解释:[5, 3] 也是有效的答案。

示例 2:

输入:nums = [-1,0]
输出:[-1,0]

示例 3:

输入:nums = [0,1]
输出:[1,0]

题目链接:260. 只出现一次的数字 III

思路:

整数数组nums中,其中恰好有两个元素只出现一次,其他元素均出现两次。这种我们通过0与数组的所有元素异或好像并不能直接得到那两个只出现一次的元素,那么我们应该怎么做呢?

第一步:我们先将0与数组的所有元素异或,此时异或之后得到的结果是那两个只出现一次的元素异或的值,我们就暂且令这个值为ret

第二步:通过将ret右移并且位与1,来找到ret二进制为1的那一位,我们暂且令这一位为k

第三步:将整数数组进行分组,我们知道异或运算符的特点:相异为1,相同才为0。所以可以根据整个特点来将整数数组进行分组,整数数组中二进制第k位为0的进入a组,二进制第k位为1的进入b组

那么只出现一次的元素会被分别分到a组与b组,出现两次的重复元素也会被分别分到a组与b组。

第三步:再通过0分别在a组与b组进行组内异或,最终a组与b组异或的结果就是那两个只出现一次的元素,如此我们便得到了那两个只出现一次元素

 

代码如下:

int* singleNumber(int* nums, int numsSize, int* returnSize){
int x = 0;
int y = 0;
int ret = 0;
for(int i = 0;i>k)&1)
    break;
}

//ret的第k位为1,证明那两个只出现一次的元素的第k位应该是1个为1,1个为0
//分离:将数组分成两组,第k位为1的为1组,第k位为0的为1组
int j = 0;
for(j=0;j>k)&1)
    {
        x^=nums[j];
    }
    //b组
    else
    {
        y^=nums[j];
    }
}
int *arr = (int*)malloc(sizeof(int)*2);
arr[0] = x;
arr[1] = y;
*returnSize = 2;
return arr;

}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/304259.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号