Middle-題目2：260. Single Number III

題目原文：

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.

題目大意：

給一個數組，裡面有兩個元素隻出現了一次，而其他數都出現了兩次，找出這兩個元素。

題目分析：

這道題是Middle-題目1的變形。

樸素解法：

用HashSet存儲每一個元素，如果元素存在于集合内就remove掉，否則add進集合内，這樣周遊完一個數組就set裡面隻剩下兩個元素。

使用位運算的解法：

設兩個單獨的數是a和b，先把所有數都異或起來，得到a⊕b，記這個數是r，而因為a≠b，是以r≠0，r對應的二進制數一定有1。再令mask=r∧￢(r-1)，得到一個比特串，mask串一定隻有一位是1，其他位都是0，這個1即是r中最低位的1.既然這一位為1，說明a和b中對應位必然一個是0一個是1。再周遊一遍這個數組，把每個數和mask求一次與，再分别異或起來，這就得到了a和b。（因為相當于分成mask所在位為0和1的兩個子數組，把這兩個子數組都異或起來自然得到了a和b。）

源碼：（language：java）

樸素解法：

public class Solution {
    public int[] singleNumber(int[] nums) {
        HashSet<Integer> set=new HashSet<Integer>();
        for(int num:nums) {
            if(set.contains(num))
                set.remove(num);
            else
                set.add(num);               
        }
        int[] array=new int[];
        int i=;
        for(int num:set)
            array[i++]=num;

        return array;


    }
}
           

位運算解法：

public class Solution {
    public int[] singleNumber(int[] nums) {
        int[] res = new int[];
        int r = ;
        for(int i=;i<nums.length;i++) {
            r = r^nums[i];
        }
        res[] = ;
        res[] = ;
        int mask = r & (~(r-));
        for(int i=;i<nums.length;i++){
            if((mask & nums[i])!=){
                res[] = res[] ^ nums[i];
            }else {
                res[] = res[] ^ nums[i];
            }
        }
        return res;
    }
}
           

成績：

樸素解法：12ms,beats 14.33%,衆數2ms,62.30%

位運算解法：2ms,beats 37.32%