[劍指offer][JAVA][面試題56 - I][第260題][位運算][HashSet]

【問題描述】 [面試題56 - I] [數組中數字出現的次數]

一個整型數組 nums 裡除兩個數字之外，其他數字都出現了兩次。請寫程式找出這兩個隻出現一次的數字。要求時間複雜度是O(n)，空間複雜度是O(1)。

 

示例 1：

輸入：nums = [4,1,4,6]
輸出：[1,6] 或 [6,1]


           

【解答思路】

1.位運算

【1，4，4，6】

• 根據異或的性質，相同異或結果為 0，相異的異或結果為 1，是以将數組中的數字做異或運算，得到兩個隻出現一次數字的異或結果。

  1 ^ 4 ^ 4 ^ 6 = 7

  

• 由于兩數字不同，異或結果不為 0，則其二進制中必然有一位是不相同的。

  方法一： 7 & i = 0 (出現0 證明可以作為分組依據 )

  

  方法二：7 & -7 = 0001

  

• 可以先找到不相同的位，就可以将數組分成兩組，再像之前那樣做異或運算。

  

class Solution {
    // 自己尋找最右邊 1 的位置
    public int[] singleNumbers(int[] nums) {
        if (nums == null || nums.length < 2) return new int[0];
        int xor = 0; // 數組第一次異或的結果，即兩個隻出現一次的數的異或結果
        for (int num : nums) xor ^= num;
        // 尋找右邊第一個 1，也就是最右邊不相同的位
        int i = 1;
        while ((i & xor) == 0){
            i <<= 1;
        }
        int[] res = new int[2];
        for (int num : nums) {
            if ((i & num) == 0) res[0] ^= num;
            else res[1] ^= num;
        }
        return res;
    }


    // 位運算 xor & （-xor）
    public int[] singleNumbers(int[] nums) {
        if (nums == null || nums.length < 2) return new int[0];
        int xor = 0; // 表示兩個隻出現一次的數字的異或結果
        for (int num : nums) xor ^= num;

        xor &= -xor;
        int[] res = new int[2];
        for (int num : nums) {
            if ((xor & num) == 0) res[0] ^= num;
            else res[1] ^= num;
        }
        return res;
    }
}


           

2. HashSet

周遊數組，遇到的數如果 HashSet 中存在，就把這個數删除。如果不存在，就把它加入到 HashSet 中。最後 HashSet 中剩下的兩個數就是我們要找的了。

時間複雜度：O(N) 空間複雜度：O(N)

public int[] singleNumber(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    for (int n : nums) {
        if (set.contains(n)) {
            set.remove(n);
        } else {
            set.add(n);
        }
    }
    int[] result = new int[2];
    int i = 0;
    for (int n : set) {
        result[i] = n;
        i++;
    }
    return result;
}

           

【總結】

1. 位運算

異或運算（^）

運算規則：0^0=0； 0^1=1； 1^0=1； 1^1=0；

即：參加運算的兩個對象，如果兩個相應位為“異”（值不同），則該位結果為1，否則為0。

5 ^ 1 = 0101 ^ 0001 = 0100 = 4

5 ^ 3 = 0101 ^ 0011 = 0110 = 6

用法

1. 翻轉指定位 對應位異或1

   X=10101110，使X低4位翻轉，用X ^0000 1111 = 1010 0001即可得到。

2. 兩個數是否相等 ==0

   5 ^ 5 = 0101 ^ 0101 = 0000 = 0

與運算（&）

運算規則：0&0=0; 0&1=0; 1&0=0; 1&1=1;

即：兩位同時為“1”，結果才為“1”，否則為0

5 & 1 = 0101 & 0001 = 0001 = 1

5 & 2 = 0101 & 0010 = 0000 = 0

用法

取指定位 對應位與1

設X=10101110，

取X的低4位，用 X & 0000 1111 = 00001110 即可得到；

或運算（|）

運算規則：0|0=0； 0|1=1； 1|0=1； 1|1=1；

即 ：參加運算的兩個對象隻要有一個為1，其值為1

用法：

指定位置置1 對應位或1

将X=10100000的低4位置1 ，用X | 0000 1111 = 1010 1111即可得到

取反運算（~）

運算規則：~1=0； ~0=1；

即：對一個二進制數按位取反，即将0變1，1變0

帶符号左移運算（<<）

若左移時舍棄的高位不包含1，則每左移一位，相當于該數乘以2(右邊補0)

3 << 1 = 0011 <<1 = 0110 = 6

帶符号右移運算（>>）

正數操作數每右移一位，相當于該數除以2

(左補0 or 補1得看被移數是正還是負)

5 >> 1 = 0101 >> 1 = 0010 = 2

5 >> 2 = 0101 >> 2 = 0001 = 1

-14 >> 2 = 11110010 >> 2 = 11111100 = -4

無符号右移運算（>>>）

5 >>> 1 = 0101 >>> 1 = 0010 = 2

-14 >>>2 =11111111 11111111 1111111111110010 >>>2 = 00111111 11111111 1111111111111100 = 1073741820

移位總結

• 正數的左移與右移，負數的無符号右移，就是相應的補碼移位所得，在高位補0即可。
• 負數的右移，就是補碼高位補1,然後按位取反加1即可。

2. 位運算 判相等換位異或^ 取位與&1 置位或|1

3. HashMap 或 HashSet常見用法

3.1 HashSet

（1）增加

public boolean add(E e);

（2）删除

public boolean remove(Object j);

（3）對比查找

public boolean contains(Object j);

（4）清空集合

public void clear();

（5）擷取長度

public int size();

3.2 HashMap

（1） 插入鍵值對資料

public V put(K key, V value)

（2）根據鍵值擷取鍵值對值資料

public V get(Object key)

（3）擷取Map中鍵值對的個數

public int size()

（4）判斷Map集合中是否包含鍵為key的鍵值對

public boolean containsKey(Object key)

（5）判斷Map集合中是否包含值為value的鍵值對

boolean containsValue(Object value)

（6）判斷Map集合中是否沒有任何鍵值對

public boolean isEmpty()

（7）清空Map集合中所有的鍵值對

public void clear()

（8）根據鍵值删除Map中鍵值對

public V remove(Object key)