LeetCode 力扣C++题解 260. 只出现一次的数字 III

LeetCode 力扣C++题解 260. 只出现一次的数字 III

题目描述：给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。（难度：中等）

进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

原题链接：260. 只出现一次的数字 III - 力扣（LeetCode） (leetcode-cn.com)

方法一：哈希表
思路与算法

我们可以使用一个哈希映射统计数组中每一个元素出现的次数。

在统计完成后，我们对哈希映射进行遍历，将所有只出现了一次的数放入答案中。

C++代码：

class Solution {
public:
    vector singleNumber(vector& nums) {
        unordered_map freq;
        for (int num: nums) {
            ++freq[num];
        }
        vector ans;
        for (const auto& [num, occ]: freq) {
            if (occ == 1) {
                ans.push_back(num);
            }
        }
        return ans;
    }
};

方法二：位运算

C++代码：

class Solution {
public:
    vector singleNumber(vector& nums) {
        int xorsum = 0;
        for (int num: nums) {
            xorsum ^= num;
        }
        // 防止溢出
        int lsb = (xorsum == INT_MIN ? xorsum : xorsum & (-xorsum));
        int type1 = 0, type2 = 0;
        for (int num: nums) {
            if (num & lsb) {
                type1 ^= num;
            }
            else {
                type2 ^= num;
            }
        }
        return {type1, type2};
    }
};