面试题 17.19. 消失的两个数字.md

面试题 17.19. 消失的两个数字

题目传送门

点击这里

解题思路

这道题正常可以用hash来做，但题目给了要求，就是一道经典位运算的题了，首先根据题意，1到N的整数当中，缺少了两个，那么给定数组的长度就是n-2，位运算首先要了解的是两个相同数字进行异或运算得到的结果是0，所以我们如果原数组的数字进行异或和再同1到N的数字进行一边异或和，最终得到的结果应该是两个缺失数字的异或和结果，即x1 ⊕ x2，另外要知道一一点，x & -x的位运算返回的是最低位的1所在的位置，一般可以通过这个来判断是否为0、奇数、偶数。在得到了最低位的1之后，二者必定其中其中一个为1，另一个为0，不然不能得到如此结果，所以可以将原先的数组中的数字分成两部分，一部分是在二进制在该位置为1的一部分是二进制在该位置为0，然后将原先的数组分割成这两部分，再对每一部分进行异或运算就能得到单独的缺失的数字。

代码

func missingTwo(nums []int) []int {
    xorSum := 0
    n := len(nums) + 2
    for _, num := range nums {
        xorSum ^= num
    }
    for i := 1; i <= n; i++ {
        xorSum ^= i
    }
    lsb := xorSum & -xorSum
    type1, type2 := 0, 0
    for _, num := range nums {
        if num&lsb > 0 {
            type1 ^= num
        } else {
            type2 ^= num
        }
    }
    for i := 1; i <= n; i++ {
        if i&lsb > 0 {
            type1 ^= i
        } else {
            type2 ^= i
        }
    }
    return []int{type1, type2}
}