分門别類刷算法，堅持，進步！
刷題路線參考：
https://github.com/chefyuan/algorithm-base
大家好，我是刷題困難戶老三，這一節我們來刷幾道很有意思的
求次數問題
，它們都有同一類非常巧妙的解法。
這種解法是什麼呢？往下看吧！
基礎知識
在開始之前，我們最好先了解一些位運算的基礎知識。
原反補碼
先簡單說一下，原碼、反碼、補碼。
一個數在計算機中的二進制表示形式, 叫做這個數的機器數。機器數是帶符号的，在計算機用一個數的最高位存放符号, 正數為0, 負數為1.
比如，十進制中的數 +3 ，假如計算機字長為8位，轉換成二進制就是00000011。如果是 -3 ，就是 10000011 。
- 原碼
原碼就是符号位加上真值的絕對值, 即用第一位表示符号, 其餘位表示值. 比如如果是8位二進制:
[+1]原 = 0000 0001
[-1]原 = 1000 0001
- 反碼
正數的反碼是其本身
負數的反碼是在其原碼的基礎上, 符号位不變，其餘各個位取反。
[+1] = [00000001]原 = [00000001]反
[-1] = [10000001]原 = [11111110]反
- 補碼
正數的補碼就是其本身
負數的補碼是在其原碼的基礎上, 符号位不變, 其餘各位取反, 最後+1. (即在反碼的基礎上+1)
[+1] = [00000001]原 = [00000001]反 = [00000001]補
[-1] = [10000001]原 = [11111110]反 = [11111111]補
補碼是人腦認識裡不太直覺的一種表示方式，之是以發明補碼，是為了讓機器以一種一緻的方式來處理加法運算。
更多知識建議閱讀《j計算機組成原理》。
與或非異或運算
在處理整型數值時，位運算符可以直接對組成整型數值的各個位進行操作。這些位運算符在位模式下工作。位運算符包括：
&
、
|
~
^
- 與（&）
對應位都為1，結果為1，否則結果為0
int a=129;
int b=128;
System.out.println("a與b的結果："+(a&b));
# 輸出
a與b的結果：128 計算過程如下:
10000001 &
10000000 =
10000000 - 或（|）
對應位隻要有一個為1，結果是1，否則就為0
int a=129;
int b=128;
System.out.println("a或b的結果："+(a|b));
# 輸出
a或b的結果是：129 10000001 |
10000000 =
10000001 - 非（~）
位為0，結果是1；位為1，結果是0
int a = 8;
System.out.println("非a的結果："+(~a));
# 輸出
非a的結果：-9 計算過程如下
//8轉換為二進制
1000
// 補符号位
01000
// 取反
10111 (補碼)
// 轉源碼除符号位取反+1
11001 - 異或（^）
對應位相同，結果是0，否則結果是1
1111 ^
0010 =
1101 移位運算
移位運算見名知意，是數字二進位的移動，我們這裡隻讨論int型的移位運算。
- << 左移運算符
數值的補碼全部左移若幹位，符号位和高位丢棄，低位補 0。
- >> 右移運算符
數值的補碼全部右移若幹位，符号位不變。
假如int是8位二進制，兩個例子如下：
10的補碼為0000 1010，左移一位變成20（0001 0100），右移一位變成5（0000 0101）
5的補碼為0000 0101，左移一位變成10（0000 1010），右移一位變成2（0000 0010）
求次數問題
LeetCode136. 隻出現一次的數字
☕ 題目：136. 隻出現一次的數字 (https://leetcode-cn.com/problems/single-number/)
❓ 難度：簡單
📕 描述：
給定一個非空整數數組，除了某個元素隻出現一次以外，其餘每個元素均出現兩次。找出那個隻出現了一次的元素。
說明：
你的算法應該具有線性時間複雜度。 你可以不使用額外空間來實作嗎？
💡思路：
哈希法
用哈希表存儲每一個元素出現的次數，最後找到出現一次的元素。
代碼如下：
public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
//存儲元素出現的次數
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
}
//周遊擷取出現次數為1的情況
for (int k : map.keySet()) {
if (map.get(k) == 1) {
return k;
}
}
return -1;
} ⏰ 時間複雜度：O(n)
🏠 空間複雜度：O(n)
位運算
題中要求空間複雜度O(1)，哈希法明顯是不合要求的。
這裡有一個全新的方法：
位運算
。
異或運算有如下特點：
- 一個數和 0 做
異或
- 一個數和其本身做
異或
-
異或
可以重複分利用
異或
運算的特性，異或數組所有元素，最後留下的那個就是隻出現一次的元素。
public int singleNumber(int[] nums) {
int ans = 0;
for (int i = 0; i < nums.length; i++) {
//異或運算
ans ^= nums[i];
}
return ans;
} 🏠 空間複雜度：O(1)
LeetCode137. 隻出現一次的數字 II
☕ 題目：137. 隻出現一次的數字 II (https://leetcode-cn.com/problems/single-number-ii/)
❓ 難度：中等
給你一個整數數組
nums
，除某個元素僅出現 一次 外，其餘每個元素都恰出現 **三次 。**請你找出并傳回那個隻出現了一次的元素。
這道題和
劍指 Offer 56 - II. 數組中數字出現的次數 II是一樣的。
第一反應還是哈希法，不用多說了，直接上代碼：
public int singleNumber(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
}
for (int k : map.keySet()) {
if (map.get(k) == 1) {
return k;
}
}
return -1;
} 好了，又到了我們的主角出場。
将我們的數的二進制位每一位相加，然後對每一位的和與3取餘：
這個原理是什麼呢？
如果其他數都出現 3 次，隻有目标數出現 1 次，那麼每一位的 1 的個數無非有這兩種情況，
- 為 3 的倍數（全為出現三次的數）
- 3 的倍數 +1（包含出現一次的數）
這個 3 的倍數 +1 的情況也就是我們的目标數的那一位。
public int singleNumber(int[] nums) {
int res = 0;
for (int i = 0; i < 32; i++) {
int count = 0;
for (int num : nums) {
//檢查第i位是否為1
if ((num >> i & 1) == 1) {
count++;
}
}
if (count % 3 != 0) {
//将第i位設為1
res = res | 1 << i;
}
}
return res;
} 🚗時間複雜度：O(n)
LeetCode260. 隻出現一次的數字 III
☕ 題目：260. 隻出現一次的數字 III (https://leetcode-cn.com/problems/single-number-iii/)
給定一個整數數組 nums，其中恰好有兩個元素隻出現一次，其餘所有元素均出現兩次。 找出隻出現一次的那兩個元素。你可以按 任意順序 傳回答案。
是一模一樣的。
這次不是一個重複的元素了，是兩個。還是先上我們樸素的哈希法。
public int[] singleNumber(int[] nums) {
int[] res = new int[2];
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
}
int index = 0;
for (int k : map.keySet()) {
if (map.get(k) == 1) {
res[index] = k;
index++;
}
}
return res;
} 位運算[5]
我們在
LeetCode136. 隻出現一次的數字
裡隻用了一個異或就找出了那個出現一次的數字。
這道題怎麼辦呢？
要是我們能把它分成兩組就好了。
怎麼分呢？
大家都知道異或運算對應位相同，結果是0，否則結果是1
我們可以根據兩個數某一位是否是0和1來把數組分為兩組。
例如數組： [12，13，14，17，14，12]
異或的結果是：13^17。
分組位找到了。
那麼怎麼借助分組位進行分組呢？
13、17的異或值，可以僅保留異或值的分組位，其餘位變為 0，例如 11100變成00100。
為什麼要這麼做呢？在第二題提到，我們可以根據 a & 1 來判斷 a 的最後一位為 0 還是為 1，是以我們将 11100變成00100之後，然後數組内的元素 x & 001 即可對 x 進行分組 。
那麼我們如何才能僅保留分組位，其餘位變為 0 呢？
可以利用 x & (-x) 來保留最右邊的 1。
public int[] singleNumber(int[] nums) {
int bitMask = 0;
//把數組中的所有元素全部異或一遍
for (int num : nums) {
bitMask ^= num;
}
//保留最右邊的1
bitMask &= -bitMask;
int[] res = {0, 0};
for (int num : nums) {
//将數組分成兩部分，每部分分别異或
if ((num & bitMask) == 0) {
res[0] ^= num;
} else {
res[1] ^= num;
}
}
return res;
} 總結
三道求次數問題就這麼做完了。
求次數問題的樸素做法是Hash法，使用Hash存儲元素出現次數。
但是Hash法空間複雜度是O(n)，如果要求O(1)的空間複雜度就不行了。
這時候就要靈活利用
位運算
的方法，位運算的關鍵在于充分了解位運算的相關應用。
簡單的事情重複做，重複的事情認真做，認真的事情有創造性地做。點贊
不迷路，咱們下期見！關注