260.只出现一次的数字-iii.py

#
# @lc app=leetcode.cn id=260 lang=python3
#
# [260] 只出现一次的数字 III
#
# https://leetcode-cn.com/problems/single-number-iii/description/
#
# algorithms
# Medium (73.42%)
# Likes:    276
# Dislikes: 0
# Total Accepted:    28.1K
# Total Submissions: 38.3K
# Testcase Example:  '[1,2,1,3,2,5]'
#
# 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
# 
# 示例 :
# 
# 输入: [1,2,1,3,2,5]
# 输出: [3,5]
# 
# 注意：
# 
# 
# 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
# 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
# 
# 
#

# @lc code=start
class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        # 异或 + 分组
        res = 0
        for n in nums:
            res ^= n
        div = 1
        while res & div == 0:
            div <<= 1
        a, b = 0, 0
        for n in nums:
            if n & div:
                a ^= n
            else:
                b ^=n
        return [a, b]

# @lc code=end