【LeetCode260】只出现一次的数字 III(分组是关键,位运算)
一、题目
二、思路
如果我们把数组分成两个子数组,每个数组都满足「恰好有一个元素只出现一次,其余所有元素均出现两次」,就可以按照之前的方法直接解决了。
(1)直接遍历一遍数组并逐一【异或】一定可以得到那两个不同元素的异或。如数组[2,2,1,1,3,4]
。这个数组的异或值最终是3 与 4 的异或值为 div = 0011 ^ 0100 = 0111。
(2)取最低位置的 ‘1’来进行对 a 与 b 的分组
div &= -div;
-div = 1000 + 0001 = 1001 (将div所有的bit反过来加1)
因此我们有 div & -div = 0111 & 1001 = 0001
(3)取得了最低为的 1 后可与进行对数组的分组,对于在 000 ‘1’这个位置有 1 的数字为一组,反之另一组,栗子中的具体分组过程:
数字 1 和 3 对应的值为 0001 与 0011,注意他们在最低位置都有0001,因此 div & 1 跟 div & 3 都会返回0001;数字 2 和 4 对应的值为 0010 与 0100 注意他们在最低位置都有没有0001,因此 div & 2 跟 div & 4 都会返回0000。
分成2个组后,每个数组里只有一个与众不同的数了,这样就回到【LeetCode136】只出现一次的数字(不能用哈希,用位运算-异或)的做法了。
三、代码
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
long div = nums[0];
for(int i = 1; i < nums.size(); i++){
div ^= nums[i]; //异或
}
int a = 0, b = 0;
//取最低位的1
div &= -div;
for(int i = 0; i < nums.size(); i++){
if(div & nums[i]){
a ^= nums[i];
}else{
b ^= nums[i];
}
}
return {a, b};
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
文章来源: andyguo.blog.csdn.net,作者:山顶夕景,版权归原作者所有,如需转载,请联系作者。
原文链接:andyguo.blog.csdn.net/article/details/123098422
- 点赞
- 收藏
- 关注作者
评论(0)