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 NumberSingle 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
}