LeetCode 260: Single Number III 解法介绍

LeetCode 问题 260 是一道有关位运算知识的题目。最佳解法可以使用 \(O(n)\) 的时间复杂度和常数的空间复杂度解决该问题。本文给出关于该问题的详细解释。

另请参见：Single Number II 问题与相应题解

题目翻译

给出一个整型数组，其中包含两个只出现一次的元素，而其他元素则每个出现两次。试图找到那两个只出现一次的元素。你可以以任意顺序返回你的答案。

再试试：你的算法应当具有线性时间复杂度。你能否使用常数空间复杂度来实现它呢？

 
示例1:
输入: nums = [1,2,1,3,2,5]
输出: [3,5]
解释:  [5, 3]也是有效答案

示例2:
输入: nums = [-1,0]
输出: [-1,0]

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


约束条件: 1 <= nums.length <= 30000

参考题解

与本道题目的姊妹题目 Single Number 与 Single Number II 不同，该问题中出现了两个仅出现一次的元素。我们不能简单地使用位异或的方法将两个元素同时捕捉到。

然而，由于两个元素 a!=b，这两个元素中一定存在至少一个二进制位的差异。我们依赖这个性质将这两个元素予以区分。

当我们使用类似从 Single Number（LeetCode 问题 136）中学到的位异或技巧将所有元素进行 XOR 操作后，我们得到的不再是一个单个数字，而是这两个数字的位异或结果：如果这个结果中有的二进制位为 1，则说明这两个数字中该二进制位存在差异（即一个数的相应位置为 0，另一个数的对应位置必为 1）。

我们将存在差异的二进制位称作第 i 位。此时，我们将情景描述为：两个所求元素在该二进制位中存在差异，一个对应位置为 0，另一个等于 1。

因此，我们容易将所有数字依据该位值为 0/1 分为两组：第一组包含第 i 位为 0 的所有元素；而第二组包含该位为 1 的所有元素。我们便很容易地将两个所求之数区分开。

此时，对第一组所有元素进行位异或操作，即可得到第一个数。同样地，对第二组所有元素进行位异或操作，即可得到第二个数。

解法示例

Golang

func singleNumber(nums []int) []int {
    var diff int
    for _, num := range nums {
        diff ^= num
    }
    
    var diffLocation int
    for true {
        if (diff%2 != 0) {
            break
        }
        diff >>= 1
        diffLocation++
    }
    
    judge := 1<<diffLocation
    
    res := []int{0, 0}
    for _, num := range nums {
        if num & judge != 0 {
            res[0] ^= num
        } else {
            res[1] ^= num
        }
    }
    
    return res
}