你知道“二分”，那你知道“三路切分”嗎？
在這里核心就是算法思想叫做"三路切分"。 “三路切分” 曾是 EMC 面試中的常客，這個名詞聽起來很高大上，但是簡單來說就是將數組切分成三部分。 我再回憶一下“快速排序”算法。
// 交換數組中兩個元素的值
function swap(a, i, j) {
const temp = a[i];
a[i] = a[j];
a[j] = temp;
}
function qsort(a, b, e) {
// 邊界處理
if (b >= e || b + 1 >= e) {
return;
}
// 第一步：劃分子結構
const mid = b + ((e - b) >> 1);
// 第二步：找到根節點，獲取信息
const x = a[mid];
let l = b;
let i = b;
let r = e - 1;
while(i <= r) {
if (a[i] < x) {
swap(a, l++, i++);
} else if (a[i] === x) {
i++;
} else {
swap(a, r--, i);
}
}
// 第三步：將根節點信息傳遞給左右子數組
qsort(a, b, l);
qsort(a, i, e);
}
// 主函數，將數組nums排序
function quickSort(nums) {
if (nums == null)
return;
qsort(nums, 0, nums.length);
return nums;
}那為什么需要“三路切分”，它的意義是什么？這里看一個例子：
輸入：[2, 1, 0]
輸出：[0, 1, 2]
如何只通過 swap 操作，將這個數組進行排序？
要求：你的時間復雜度需要是 O(N)，空間復雜度需要是 O(1)。在快速排序的時候，我們通過一個整數 x 將數組切分成小于、等于、大于三部分。問題的關鍵就是如何在時間復雜度 O(N)，空間復雜度 O(1) 條件下完成這個操作。
對于快速排序而言，通過一個整數 x 將數組切分成：
- 小于 x 部分；
- 等于 x 的部分；
- 大于 x 的部分；
本質上來說，其實包含四部分：
- 小于 x 部分；
- 等于 x 的部分；
- 還未處理數的部分；
- 大于 x 的部分；
圖片
我們假設這四部分分別對于四個區間：
- 小于 x 部分：[0, l)；
- 等于 x 的部分[l, i)；
- 還未處理數的部分[i, r]；
- 大于 x 的部分(r, length)；
圖片
在進行排序是，我們劃分結構讀取的是 [i, r) 區間的值。 在 [i, r) 區間中的值 x 取值只可能是下面 3 種情況：
- x 屬于 [0, l) 區間；
- x 屬于 [l, i) 區間；
- x 屬于 (r, length) 區間；
快速排序的目的就是將[i, r]區間的取，全部插入到其他區間，完成排序操作。
1. x 屬于 [0, l) 區間
如果 x 屬于 [0, l) 區間，那么我們就需要將 x 插到 [0, l) 區間。
圖片
將 x 插入到 [0, l) 這個區間除了像插入排序一樣一個一個地移動，還有沒有更好的辦法呢？
答案是，有，我并不需要一個一個移動！因為 [l, i) 區間里面全都是等于 x 的部分，只需要將的 nums[l] 與 nums[i] 進行交換即可。這就回答了第一個問題？為什么我們在節點排序處理是通過 swap 操作？
圖片
這時候整個[l, i) 區間整體向右平移一步，整個[i, r) 區間也整體向右平移一步。所以需要執行 l++, i++。
if (a[i] < x) {
swap(a, l++, i++);
}2. 如果 x 屬于 [l, i) 區間
如果 x 屬于 [l, i) 區間，也就是等于 x 的部分，那么我們就需要將 x 插到 [l, i) 區間，這里就比較簡單了，只需要為 [l, i) 區間擴展一下就好了。相當于在 [l, i) 區間添加了一個元素，所以需要執行 i++。
圖片
else if (a[i] === x) {
i++;
}3. 如果 x 屬于 (r, length) 區間
如果 x 屬于 (r, length) 區間，也就是大于 x 的部分，那么我們就需要將 x 插到 (r, length) 區間，相當于 (r, length)區間向左平移了一步，這時候 r--。
圖片
else {
swap(a, r--, i);
}最終狀態：所有的數都被處理之后，[i, r] 區間肯定為空集。由于兩邊都是取閉，那么必然當 i > r 的時候，[i, r] 才是空集。原本的四個區間，變成三個區間。
- [0, l) 小于 x 的區間
- [l, i) 等于 x 的區間
- [i, length) 大于 x 的區間。
注意此時由于 i > r，實際上 i = r + 1，那么區間 (r, length) 就是 [i, length)。 由于最終狀態是將一個亂序的數組切分成三部分，所以這個方法又叫三路切分。
接下來我們看一個例子：
列1：只出現一次的數字
給你一個 非空 整數數組 nums ，除了某個元素只出現一次以外，其余每個元素均出現兩次。找出那個只出現了一次的元素。 你必須設計并實現線性時間復雜度的算法來解決此問題，且該算法只使用常量額外空間。
示例 1 ：
輸入：nums = [2,2,1]
輸出：1
示例 2 ：
輸入：nums = [4,1,2,1,2]
輸出：4
示例 3 ：
輸入：nums = [1]
輸出：1這道題目想想用“三路切分”如何實現？
任意選中一個數字 x ，將數組分成三份，那么是不是會出現三種情況？
- 第一種：只出現一次的數字在 x 左邊，那么左邊區域的長度為奇數，因為其他的數都是出現了兩次。
- 第二種：選中的 x 就是只出現一次的數組，左右兩邊區間長度都為偶數。
- 第三種：只出現一次的數在右邊，那么右區間的長度為奇數。
通過分析可知 3 種情況中，只有第二種情況得到了結果。而第一種情況只出現 1 次的數在左區間時，只需要遞歸地處理左區間；第三種情況只出現 1 次的數在右區間時，只需要遞歸地處理右區間。
function swap(A, i, j) {
const t = A[i];
A[i] = A[j];
A[j] = t;
}
function threeSplit(a, b, e) {
// 邊界情況
if (b >= e) {
return 0;
}
/*********************核心代碼****************************/
// 第一步：劃分子結構
const mid = b + ((e - b) >> 1);
// 第二步：獲取根節點信息 x
const x = a[mid];
// 根據 x 將數組一分為三 【三路切分】
let l = b;
let i = b;
let r = e - 1;
while(i <= r) {
if (a[i] < x) {
// 小于 x 的部分
swap(a, l++, i++);
} else if (a[i] === x) {
// 等于 x 的部分
i++;
} else {
// 大于 x 的部分
swap(a, r--, i);
}
}
// 第三步：將根節點的信息傳遞左右子子樹
// 切分完畢之后，只有三個區間
// [b, l) [l, i) [i, N)
// 中間區間
if ((i - l) === 1) {
return a[l]
}
// 左區間
if (((l - b) % 2) == 1) {
return threeSplit(a, b, l);
}
// 右區間
return threeSplit(a, i, e);
/*********************核心代碼****************************/
}
// 主函數
function main(nums) {
if (nums == null || nums.length <= 0) {
return 0;
}
return threeSplit(nums, 0, nums.length);
}總結
盡管與位運算相比，這種解法算不上最優，不過也不失一種有趣的解法。數組其實是另外一種形式的二叉樹，只不過有時候需要我們動態地把左/右子樹給切分出來，不同的切分方式，可以解決不同的問題。
