[劍指offer] 數組中隻出現一次的數字

本文首發于我的個人部落格： 尾尾部落

題目描述

一個整型數組裡除了兩個數字之外，其他的數字都出現了偶數次。請寫程式找出這兩個隻出現一次的數字。

解題思路

法一：大家都能想到的HashMap法

法二：異或法

任何一個數字異或它自己都等于0。

如果數組中隻一個數字是隻出現一次的，其他數字都是成雙成對出現的，那麼我們從頭到尾依次異或數組中的每個數字，最終的結果剛好就是那個隻出現一次的數字，因為那些成對出現兩次的數字全部在異或中抵消了。

那麼回到我們的題目，因為有兩個隻出現一次的數字，是以我們可以試着把原數組分成兩個子數組，使得每個數組包含一個隻出現一次的數字，而其他數字都成對出現兩次。如果這樣拆分成兩個數組，那麼我們就可以按照之前的辦法分别對兩個數組進行異或運算找出兩個隻出現一次的數字。

問題來了，如何進行分組呢？

我們還是從頭到尾依次異或數組中的每個數字，那麼最終得到的結果就是兩個隻出現一次的數字異或的結果。由于這兩個數字不一樣，是以異或的結果至少有一位為1，我們在結果數字中找到第一個為1的位置，記為index位，現在我們以第index位是不是1為标準把原數組拆分成兩個子數組，第一個子數組中的數組第index位都為1，第二個子數組中的數組第index位都為0，那麼隻出現一次的數字将被配置設定到兩個子數組中去，于是每個子數組中隻包含一個出現一次的數字，而其他數字都出現兩次。這樣我們就可以用之前的方法找到數組中隻出現一次的數字了。

參考代碼

法一：HashMap

import java.util.HashMap;
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        HashMap<Integer, Integer> temp = new HashMap<Integer, Integer>();
        for(int i = 0; i < array.length; i++){
            if(temp.containsKey(array[i]))
                temp.remove(array[i]);
            else
                temp.put(array[i], 1);
        }
        int [] a = new int [array.length];
        int i = 0;
        for(Integer k: temp.keySet()){
            a[i] = k;
            i++;
        }
        num1[0] = a[0];
        num2[0] = a[1];
    }
}
           

public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        num1[0] = 0;
        num2[0] = 0;
        if(array.length == 0)
            return;
        int num = 0;
        for(int i = 0; i < array.length; i++){
            num ^= array[i];
        }
        int index = 0;
        while((num & 1) == 0 && index < 8){
            num = num >> 1;
            index ++;
        }
        
        for(int i = 0; i < array.length; i++){
            if(isa1(array[i], index))
                num1[0] ^= array[i];
            else
                num2[0] ^= array[i];
        }
    }
    
    public boolean isa1(int i, int index){
        i = i >> index;
        return (i & 1) == 1;
    }
}