【Leetcode】：Single Number III问题 in Go语言

u013564276 · · 1421 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

The order of the result is not important. So in the above example, [5, 3] is also correct.

Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

题目的大意是：给定一个数组，数组中的数除了两个互不相同的数外，其余数两两成对出现，现在要找出这两个数

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

这道题拿在手上没什么简单的思路，参考了别人的结果“http://www.jianshu.com/p/402622b8ad43”

简要说下解题的思路，首先对所有数进行异或运算，那么相同的就会抵消掉，得到的结果就是两个相异的数a和b的异或，这个结果当作diff

然后求 (-diff & diff) 这个式子能得到二进制中只有一个1的数，这个1的位置代表着在这个位置上，a和b是不同的，那么就可以按照这个不同，

将所有数分为两组，第一组是该位置上与a相同，第二组是该位置上与b相同。

func singleNumber(nums []int) []int {    
    diff := 0
    for _, v := range nums {
        diff = diff ^ v
    }
    //得到的diff表示两个不同的数的按位异或的结果
    diff = -diff & diff
    result := make([]int, 2)
    for _, v := range nums {
        if diff & v == 0 {
            result[0] = result[0] ^ v 
        } else {
            result[1] = result[1] ^ v
        }
    }
    return result
}

有疑问加站长微信联系（非本文作者）