影音體驗(yàn)是真的強(qiáng) 簡單聊聊iQOO Pad
大公司的好處就是產(chǎn)品線豐富，非常細(xì)分化的東西也能給你做出來，例如早先我們看到了新的vivo Pad2，之后我們又在iQOO Neo8 Pro的發(fā)布會上看到了iQOO的首款平板產(chǎn)品iQOO Pad。雖
在這里核心就是算法思想叫做"三路切分"。 “三路切分” 曾是 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é)點(diǎn)，獲取信息 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é)點(diǎn)信息傳遞給左右子數(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ù)組進(jìn)行排序？要求：你的時間復(fù)雜度需要是 O(N)，空間復(fù)雜度需要是 O(1)。在快速排序的時候，我們通過一個整數(shù) x 將數(shù)組切分成小于、等于、大于三部分。問題的關(guān)鍵就是如何在時間復(fù)雜度 O(N)，空間復(fù)雜度 O(1) 條件下完成這個操作。
對于快速排序而言，通過一個整數(shù) x 將數(shù)組切分成：
本質(zhì)上來說，其實(shí)包含四部分：
圖片
我們假設(shè)這四部分分別對于四個區(qū)間：
圖片
在進(jìn)行排序是，我們劃分結(jié)構(gòu)讀取的是 [i, r) 區(qū)間的值。 在 [i, r) 區(qū)間中的值 x 取值只可能是下面 3 種情況：
快速排序的目的就是將[i, r]區(qū)間的取，全部插入到其他區(qū)間，完成排序操作。
如果 x 屬于 [0, l) 區(qū)間，那么我們就需要將 x 插到 [0, l) 區(qū)間。
圖片
將 x 插入到 [0, l) 這個區(qū)間除了像插入排序一樣一個一個地移動，還有沒有更好的辦法呢？
答案是，有，我并不需要一個一個移動！因?yàn)?[l, i) 區(qū)間里面全都是等于 x 的部分，只需要將的 nums[l] 與 nums[i] 進(jìn)行交換即可。這就回答了第一個問題？為什么我們在節(jié)點(diǎn)排序處理是通過 swap 操作？
圖片
這時候整個[l, i) 區(qū)間整體向右平移一步，整個[i, r) 區(qū)間也整體向右平移一步。所以需要執(zhí)行 l++, i++。
if (a[i] < x) { swap(a, l++, i++);}如果 x 屬于 [l, i) 區(qū)間，也就是等于 x 的部分，那么我們就需要將 x 插到 [l, i) 區(qū)間，這里就比較簡單了，只需要為 [l, i) 區(qū)間擴(kuò)展一下就好了。相當(dāng)于在 [l, i) 區(qū)間添加了一個元素，所以需要執(zhí)行 i++。
圖片
else if (a[i] === x) { i++;}如果 x 屬于 (r, length) 區(qū)間，也就是大于 x 的部分，那么我們就需要將 x 插到 (r, length) 區(qū)間，相當(dāng)于 (r, length)區(qū)間向左平移了一步，這時候 r--。
圖片
else { swap(a, r--, i);}最終狀態(tài)：所有的數(shù)都被處理之后，[i, r] 區(qū)間肯定為空集。由于兩邊都是取閉，那么必然當(dāng) i > r 的時候，[i, r] 才是空集。原本的四個區(qū)間，變成三個區(qū)間。
注意此時由于 i > r，實(shí)際上 i = r + 1，那么區(qū)間 (r, length) 就是 [i, length)。 由于最終狀態(tài)是將一個亂序的數(shù)組切分成三部分，所以這個方法又叫三路切分。
接下來我們看一個例子：
給你一個 非空 整數(shù)數(shù)組 nums ，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素。 你必須設(shè)計(jì)并實(shí)現(xiàn)線性時間復(fù)雜度的算法來解決此問題，且該算法只使用常量額外空間。
示例 1 ：輸入：nums = [2,2,1]輸出：1示例 2 ：輸入：nums = [4,1,2,1,2]輸出：4示例 3 ：輸入：nums = [1]輸出：1這道題目想想用“三路切分”如何實(shí)現(xiàn)？
任意選中一個數(shù)字 x ，將數(shù)組分成三份，那么是不是會出現(xiàn)三種情況？
通過分析可知 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é)點(diǎn)信息 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é)點(diǎn)的信息傳遞左右子子樹 // 切分完畢之后，只有三個區(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);}盡管與位運(yùn)算相比，這種解法算不上最優(yōu)，不過也不失一種有趣的解法。數(shù)組其實(shí)是另外一種形式的二叉樹，只不過有時候需要我們動態(tài)地把左/右子樹給切分出來，不同的切分方式，可以解決不同的問題。
本文鏈接：http://www.tebozhan.com/showinfo-26-12682-0.html你知道“二分”，那你知道“三路切分”嗎？
聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請聯(lián)系：2376512515@qq.com 津ICP備18001702號
津公網(wǎng)安備 12010102000574號