leetcode_single number

leetcode_single number

題目描述

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory

注：一組數每個數都出現兩次除了其中某個數，請找出這個只出現一次的數，不適用額外空間。

解析思路

關於計數問題常考慮hashmap，可以通過鍵值對應進行計數，然後遍歷查找只出現一次的數據，時間復雜度和空間復雜度都是O(N),這裡題目要求額外空間復雜度O(1),一種方法是遍歷數組元素，全部數組元素進行異或運算，最後結果就是那個只出現一次的數據，我們可以自己寫幾組測試數據分析下，基本思想就是 A^B^C^B^C = A ，這裡我們不使用這種方法，因為leetcode上還有一道題目是數組中元素除了某個元素只出現一次外，其他元素都出現三次，然後讓我們尋找這個元素，這樣的話，上述異或方法就不適用了。

我們的思路是將每個數看成二進制序列，int型32位即可表示(當然程序中要考慮正負數問題),我們這裡主要講述思想，明白了之後具體細節可以參考代碼理解。我們對N個數的bit0~bit31分別進行求和運算，求和mod2運算(對於出現k次則就是求和mod k)，也就是N個數的bit0疊加得到結果的bit0，N個數的bit1疊加得到結果的bit1，類似地我們得到結果的bit0….bit31,(高低位自行設定，保持一致)然後組成最終結果。

我們以bit0為例進行分析，N個數中假設除了目標數外每個數都出現K此，假設除了目標數外的N-1個數中有x個數bit0為0，N-1-x 個數bit0 為1，目標數的bit0 為 b，則求和結果為（N-1-x）K +b ,求余後得到b，也就是目標數的bit0，所以按照上述方法可以得到目標數的二進制序列。具體編碼中要使用移位運算和與運算，時間復雜度O(n).

詳細代碼

public int singleNumber(int[] A) 
{
    //r is the return value
    int r=0;
    int mask = 1;
    for(int i=1;i<=32;i++)
    {
        int bit = 0;
        for(int j=0;j>(i-1);

            //cuz java doesn't has unsigned int, we should deal with the negative integer
            if(A[j] <0)
            {
                tmpbit = tmpbit&1;
            }
            bit = (bit+tmpbit)%2;
        }
        mask = mask<<1;
        if(bit == 1)
        {
            r = r|(bit<<(i-1));
        }
    }
    return r;
}