leetcode260. Single Number III

Terry_Tai 發(fā)布于2019-08-15 14:19 / 278人閱讀

摘要：要求我們找到這兩個(gè)數(shù)字。舉例解釋一下第二個(gè)位運(yùn)算一個(gè)數(shù)的負(fù)數(shù)是通過(guò)計(jì)算其正數(shù)的補(bǔ)碼獲得的。比如的八位二進(jìn)制為，那么其反碼為，再在反碼上加一得到其補(bǔ)碼也就是的二進(jìn)制形式。從而獲得二進(jìn)制最右側(cè)的位置。

題目要求

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?

假設(shè)一個(gè)整數(shù)數(shù)組中，除了兩個(gè)數(shù)字以外，所有的數(shù)字都出現(xiàn)了兩遍。要求我們找到這兩個(gè)數(shù)字。

可以先參考Single Number I 和 Single Number II。

思路與代碼

這里需要了解兩個(gè)位運(yùn)算的重要知識(shí)：

a^b^b = a 即b^b=0
a&(-a)能夠獲得a的二進(jìn)制形式的最右側(cè)的1的位置。

舉例解釋一下第二個(gè)位運(yùn)算：
一個(gè)數(shù)的負(fù)數(shù)是通過(guò)計(jì)算其正數(shù)的補(bǔ)碼獲得的。比如5的八位二進(jìn)制為00000101，那么其反碼為11111010，再在反碼上加一得到其補(bǔ)碼11111011也就是-5的二進(jìn)制形式。
那么我們可以知道，一個(gè)數(shù)與其反碼的與運(yùn)算，得出的結(jié)果一定為0。而反碼加一則代表著將原數(shù)的最后一位1在反碼上也置為1。從而獲得二進(jìn)制最右側(cè)1的位置。

    public int[] singleNumber(int[] nums) {
       int diff = 0;
        for(int num : nums){
            diff ^= num;
        }
        
        diff &= -diff;
        
        int[] result = {0, 0};
        for(int num : nums){
            if((num & diff) == 0){
                result[0] ^= num;
            }else{
                result[1] ^= num;
            }
        }
        return result; 
    }

想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~