56 - I. 数组中数字出现的次数.md

解题思路

分组异或

假设结果为 [a, b] 将 nums 数组中所有值挨个异或（^） 相同数抵消，最终结果 sum 为 a^b 找到 sum 二进制的最右边的 1 作为 mask，这个数肯定能区分 a b 其中 a 与一些数异或 b 与另一些数异或 这样就能分别得到 a b

func singleNumbers(nums []int) []int {
    // 挨个异或得到 a^b
    sum := 0
    for _, v := range nums {
        sum ^= v
    }
    // 找到 sum 中二进制最右边的 1
    mask := 1
    for sum & mask == 0 {
        mask <<= 1
    }
    // 分别异或找到 a b
    a, b := 0, 0
    for _, v := range nums {
        if v & mask == 0 {
            a ^= v
        } else {
            b ^= v
        }
    }
    return []int{a, b}
}