260. 只出现一次的数字 III

English Version

题目描述

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

 

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

 

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解法

Python3

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        eor = 0
        for x in nums:
            eor ^= x
        lowbit = eor & (-eor)
        ans = [0, 0]
        for x in nums:
            if (x & lowbit) == 0:
                ans[0] ^= x
        ans[1] = eor ^ ans[0]
        return ans

Java

class Solution {
    public int[] singleNumber(int[] nums) {
        int eor = 0;
        for (int x : nums) {
            eor ^= x;
        }
        int lowbit = eor & (-eor);
        int[] ans = new int[2];
        for (int x : nums) {
            if ((x & lowbit) == 0) {
                ans[0] ^= x;
            }
        }
        ans[1] = eor ^ ans[0];
        return ans;
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumber = function (nums) {
    let eor = 0;
    for (const x of nums) {
        eor ^= x;
    }
    const lowbit = eor & -eor;
    let ans = [0];
    for (const x of nums) {
        if ((x & lowbit) == 0) {
            ans[0] ^= x;
        }
    }
    ans.push(eor ^ ans[0]);
    return ans;
};

C++

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        long long eor = 0;
        for (int x : nums) eor ^= x;
        int lowbit = eor & (-eor);
        vector<int> ans(2);
        for (int x : nums)
            if ((x & lowbit) == 0) ans[0] ^= x;
        ans[1] = eor ^ ans[0];
        return ans;
    }
};

Go

func singleNumber(nums []int) []int {
	eor := 0
	for _, x := range nums {
		eor ^= x
	}
	lowbit := eor & (-eor)
	ans := make([]int, 2)
	for _, x := range nums {
		if (x & lowbit) == 0 {
			ans[0] ^= x
		}
	}
	ans[1] = eor ^ ans[0]
	return ans
}

...