【LeetCode】260. 只出现一次的数字 III

260. 只出现一次的数字 III（中等）

在这里插入图片描述

思路

这道题是136. 只出现一次的数字的进阶版，需要找出两个仅出现一次的元素。有了上一题的基础，我们很容易就想到要用异或来解决，但是由于这题最终会剩下两个不同的元素，因此异或的结果 temp 肯定不为 0，那么如何解决呢？
我们可以利用 temp & (-temp) ，得到 temp 最低位的 1 ，这里的 1 说明了这两个元素在该比特位上不相同，否则该比特位的异或结果肯定为 0 。因此，我们可以从该比特位入手，设置一个 mask 表示异或结果最低位的 1。
接着，我们利用 mask ，按照元素该比特位是 1 或 0，将数组 nums 分成两部分，那么两个不同的元素肯定被分在不同的组，此时问题就简化成「一个整数数组中，其中恰好有一个元素只出现一次，其余所有元素均出现两次」，那么就回到了一开始的问题： 136. 只出现一次的数字。
最后，如何利用 mask 呢？由于mask 只有一个 1 ，其余位置均为 0，因此将它和 nums 中的元素按位与 ，如果该比特位为 0 ，那么该元素和 mask 按位与的结果为 0；否则不为 0 。

代码

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> ans(2, 0);
        long temp = 0;
        for(int n : nums){
            // 最终得到两个仅出现一次的元素的异或结果
            temp ^= n; 
        }
        
        // 获取最低位的1 说明该比特位两个元素不同
        int mask = temp & (-temp);
       
        // 将nums的数字按照该比特位分为两组
        // 每组中都有一个仅出现一次的元素
        for(int n : nums){
            if((n & mask) == 0){
                ans[0] ^= n;
            }else{
                ans[1] ^= n;
            }
        }
        return ans;
    }
};