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