260. Single Number III

260. Single Number III

Medium

3945186Add to ListShare

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Example 1:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

Example 2:

Input: nums = [-1,0]
Output: [-1,0]

Example 3:

Input: nums = [0,1]
Output: [1,0]

Constraints:

• 2 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• Each integer in nums will appear twice, only two integers will appear once.

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        """
        sorted(Solution().singleNumber([1, 2, 1, 3, 2, 5])) == [3, 5]
        
        参考别人的解题思路：假设a,b为单独的2个数，对nums所有数进行异或，可以得到 d=a^b 的值

        方法1：找到d中第一个二进制位为1的位数k，再次对nums数组的数在位数k为1或者为0进行分组，a,b肯定落在单独的一边
        int k = 0;
        while(!(sum >> k & 1)) k++;
        if(x >> k & 1)

        采用方法2：d &（-d）, 可以找到最低位为1的数，接着同方法1分组
        时间复杂度：O(n) 空间复杂度：O(1)

        如 a=3,b=5 d=a^b=6  d &（-d）= 2 可以找到最低位为1的数
        正数转负数 总结过程：          6 = 0 110 （原码）
        a.最高位改成1                1 110 负数二进制表示
        b.除了最高位，其他位取反       1 001
        c.结果+1                   1 010
        d.得到的结果就是对应的负值     -6 = 1 010  负数在机器中以补码形式保存
        负数转正数反之
        """

        d = 0
        for i in nums:
            d ^= i
        # 找到最低位为1的数
        d &= -d
        result = [0, 0]
        for i in nums:
            if i & d == 0:
                result[0] ^= i
            else:
                result[1] ^= i
        return result