首页 > 代码库 > LeetCode 260. Single Number III

LeetCode 260. Single Number III

转载请注明出处:http://www.cnblogs.com/liangyongrui/p/6354552.html 

 

异或的妙用。

 

一开始读题不仔细,以为有很多的孤立数字。

没想到就两个- -

 

然后参考了别人的思路。

 

具体见代码:

    public int[] singleNumber(int[] nums) {
        // Pass 1 : 
        // 把所有的数字相异或,这相当于对两个只出现了一次的数字做异或
        int diff = 0;
        for (int num : nums) {
            diff ^= num;
        }
        // 得到一个为1的位(准确说得到了最后一个)
        // 由于该位为1,也就是两个数中,有一个数这个位为1,另一个为0
        diff &= -diff;
        
        // Pass 2 :
        int[] rets = {0, 0}; // this array stores the two numbers we will return
        for (int num : nums) {
            //分别相与归类 
            if ((num & diff) == 0) { // the bit is not set
                rets[0] ^= num;
            }
            else { // the bit is set
                rets[1] ^= num;
            }
        }
        return rets;
    }

 

LeetCode 260. Single Number III