leetcode:260. 只出现一次的数字 III

题目

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number-iii

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

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

示例 1：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：

输入：nums = [-1,0]
输出：[-1,0]
示例 3：

示例 3：

输入：nums = [0,1]
输出：[1,0]
提示：

提示：

2 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
除两个只出现一次的整数外，nums 中的其他数字都出现两次

解法

使用字典和列表，遍历，如果遍历时候只出现一次时候，导入到列表中，如果出现两次及以上，从列表删除该元素

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        res = []
        count = {}
        for num in nums:
            if num not in count:
                count[num] = ''
            else:
                del count[num]
        for k in count:
            res.append(k)
        return res

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

解法二，位运算，异或。如果是出现两次的数字，异或的时候为0，最终的异或结果表明的是剩下的两个出现一次的异或结果，并使用low bit算法(lowbit(n)定义为非负整数n在二进制表示下“最低位的1及后面的所有0”构成的数值)找到一个二进制位用于区分二个数，然后再次异或，剩下来的就是该出现一次的元素

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor_sum = 0
        # 得到两个只出现一次的数的异或
        for num in nums:
            xor_sum ^= num 
        # 通过 low bit算法，得到最低一位等于1的二进制数
        low_bit = xor_sum & (-xor_sum)

        first, second = 0, 0
        for num in nums:
            if num & low_bit:
                first ^= num 
            else:
                second ^= num 
        return [first, second]

class Solution {
public:
    vector<int> singleNumber(vector<int>& 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};
    }
};

复杂度分析

时间复杂度： O(n), O(n)
空间复杂度： O(n), O(1)

参考

原文链接：https://blog.csdn.net/uncle_ll/article/details/121058769