Leetcode 260. 只出现一次的数字 III

最新推荐文章于 2024-05-19 16:33:38 发布

wenkun97

最新推荐文章于 2024-05-19 16:33:38 发布

阅读量140

点赞数

分类专栏：算法题_位运算

本文链接：https://blog.csdn.net/hello_my_coder/article/details/104204519

版权

算法题_位运算专栏收录该内容

2 篇文章

订阅专栏

题目描述：
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5]
输出: [3,5]

tips:先用一遍异或，找出1位为1的位置，然后根据这一位将数组分为两部分，再分别进行异或
注意： == != 等于/不等于的优先级比
& 按位与较高

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xor_res=0;
        int num1=0,num2=0;
        for (int i = 0; i < nums.size(); i++)
        {
            xor_res^=nums[i];
        }
        int bit1=1;
        while ((xor_res&1)==0)
        {
            xor_res>>=1;
            bit1<<=1;
        }
        for (int i = 0; i < nums.size(); i++)
        {
            if((nums[i]&bit1)!=0) {
                num1^=nums[i];
            } else {
                num2^=nums[i];
            }
        }
        vector<int> res;
        res.push_back(num1);
        res.push_back(num2);
        return res;
    }
};