2023年Q2用戶偏好榜：12+256G版本成新主流
3月份的性能榜、性價比榜和好評榜之后，就要輪到2023年的第二季度偏好榜了，上半年的新機潮已經過去，最明顯的肯定就是大內存和存儲的機型了，另外部分中端機也取消了屏幕塑料支架
在這里核心就是算法思想叫做"三路切分"。 “三路切分” 曾是 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 將數組切分成：
本質上來說，其實包含四部分：
圖片
我們假設這四部分分別對于四個區間：
圖片
在進行排序是，我們劃分結構讀取的是 [i, r) 區間的值。 在 [i, r) 區間中的值 x 取值只可能是下面 3 種情況：
快速排序的目的就是將[i, r]區間的取，全部插入到其他區間，完成排序操作。
如果 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++);}如果 x 屬于 [l, i) 區間，也就是等于 x 的部分，那么我們就需要將 x 插到 [l, i) 區間，這里就比較簡單了，只需要為 [l, i) 區間擴展一下就好了。相當于在 [l, i) 區間添加了一個元素，所以需要執行 i++。
圖片
else if (a[i] === x) { i++;}如果 x 屬于 (r, length) 區間，也就是大于 x 的部分，那么我們就需要將 x 插到 (r, length) 區間，相當于 (r, length)區間向左平移了一步，這時候 r--。
圖片
else { swap(a, r--, i);}最終狀態：所有的數都被處理之后，[i, r] 區間肯定為空集。由于兩邊都是取閉，那么必然當 i > r 的時候，[i, r] 才是空集。原本的四個區間，變成三個區間。
注意此時由于 i > r，實際上 i = r + 1，那么區間 (r, length) 就是 [i, length)。 由于最終狀態是將一個亂序的數組切分成三部分，所以這個方法又叫三路切分。
接下來我們看一個例子：
給你一個 非空 整數數組 nums ，除了某個元素只出現一次以外，其余每個元素均出現兩次。找出那個只出現了一次的元素。 你必須設計并實現線性時間復雜度的算法來解決此問題，且該算法只使用常量額外空間。
示例 1 ：輸入：nums = [2,2,1]輸出：1示例 2 ：輸入：nums = [4,1,2,1,2]輸出：4示例 3 ：輸入：nums = [1]輸出：1這道題目想想用“三路切分”如何實現？
任意選中一個數字 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);}盡管與位運算相比，這種解法算不上最優，不過也不失一種有趣的解法。數組其實是另外一種形式的二叉樹，只不過有時候需要我們動態地把左/右子樹給切分出來，不同的切分方式，可以解決不同的問題。
本文鏈接：http://www.www897cc.com/showinfo-26-12682-0.html你知道“二分”，那你知道“三路切分”嗎？
聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權所有 sitemap.xml
違法及侵權請聯系：2376512515@qq.com 津ICP備18001702號
津公網安備 12010102000574號