LeetCode 260. 只出现一次的数字 III（位运算）
LeetCode 260. 只出现一次的数字 III（位运算）
Michael阿明
发布于 2020-07-13 15:11:15
发布于 2020-07-13 15:11:15
文章被收录于专栏：Michael阿明学习之路
1. 题目
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]注意：
结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
类似题目 LeetCode 137. 只出现一次的数字 II（位运算） LeetCode 136. 只出现一次的数字（异或^）
2. 解题
- 先将所有数字异或，等同于那2个不同的数异或 bit
- 在将上面结果取负并与自己与 bit = bit & -bit，得到 bit 为1的最低位（即那2个数不同的二进制位）
- 在将给的数组每个数与 bit &，将数组分成2部分，2部分各自做异或^ ，即可得到2个数
关于第二步的举例：8,13 1000 1101 ^ 0101 bit bit & -bit 0001
假如 bit = 1100 bit & -bit = 0100（得到的是最低位的1）
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int bit = 0, i, n1 = 0, n2 = 0;
for(i = 0; i < nums.size(); ++i)
bit ^= nums[i];
bit &= (-bit);
for(i = 0; i < nums.size(); ++i)
{
if((bit & nums[i]) == 0)//内层括号！！！不能少
n1 ^= nums[i];
else
n2 ^= nums[i];
}
return {n1, n2};
}
};
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/09/21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
