Find N3入網(wǎng)：最高支持16+1TB
OPPO將于近期登場(chǎng)的Find N3折疊屏目前已經(jīng)正式入網(wǎng)，型號(hào)為PHN110。本次Find N3在外觀方面相比前兩代有很大的變化，不再是小號(hào)的橫向折疊屏，而是跟別的廠商一樣采用了較為常見(jiàn)的
在這里核心就是算法思想叫做"三路切分"。 “三路切分” 曾是 EMC 面試中的常客，這個(gè)名詞聽(tīng)起來(lái)很高大上，但是簡(jiǎn)單來(lái)說(shuō)就是將數(shù)組切分成三部分。 我再回憶一下“快速排序”算法。
// 交換數(shù)組中兩個(gè)元素的值 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;}那為什么需要“三路切分”，它的意義是什么？這里看一個(gè)例子：
輸入：[2, 1, 0]輸出：[0, 1, 2]如何只通過(guò) swap 操作，將這個(gè)數(shù)組進(jìn)行排序？要求：你的時(shí)間復(fù)雜度需要是 O(N)，空間復(fù)雜度需要是 O(1)。在快速排序的時(shí)候，我們通過(guò)一個(gè)整數(shù) x 將數(shù)組切分成小于、等于、大于三部分。問(wèn)題的關(guān)鍵就是如何在時(shí)間復(fù)雜度 O(N)，空間復(fù)雜度 O(1) 條件下完成這個(gè)操作。
對(duì)于快速排序而言，通過(guò)一個(gè)整數(shù) x 將數(shù)組切分成：
本質(zhì)上來(lái)說(shuō)，其實(shí)包含四部分：
圖片
我們假設(shè)這四部分分別對(duì)于四個(gè)區(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) 這個(gè)區(qū)間除了像插入排序一樣一個(gè)一個(gè)地移動(dòng)，還有沒(méi)有更好的辦法呢？
答案是，有，我并不需要一個(gè)一個(gè)移動(dòng)！因?yàn)?[l, i) 區(qū)間里面全都是等于 x 的部分，只需要將的 nums[l] 與 nums[i] 進(jìn)行交換即可。這就回答了第一個(gè)問(wèn)題？為什么我們?cè)诠?jié)點(diǎn)排序處理是通過(guò) swap 操作？
圖片
這時(shí)候整個(gè)[l, i) 區(qū)間整體向右平移一步，整個(gè)[i, r) 區(qū)間也整體向右平移一步。所以需要執(zhí)行 l++, i++。
if (a[i] < x) { swap(a, l++, i++);}如果 x 屬于 [l, i) 區(qū)間，也就是等于 x 的部分，那么我們就需要將 x 插到 [l, i) 區(qū)間，這里就比較簡(jiǎn)單了，只需要為 [l, i) 區(qū)間擴(kuò)展一下就好了。相當(dāng)于在 [l, i) 區(qū)間添加了一個(gè)元素，所以需要執(zhí)行 i++。
圖片
else if (a[i] === x) { i++;}如果 x 屬于 (r, length) 區(qū)間，也就是大于 x 的部分，那么我們就需要將 x 插到 (r, length) 區(qū)間，相當(dāng)于 (r, length)區(qū)間向左平移了一步，這時(shí)候 r--。
圖片
else { swap(a, r--, i);}最終狀態(tài)：所有的數(shù)都被處理之后，[i, r] 區(qū)間肯定為空集。由于兩邊都是取閉，那么必然當(dāng) i > r 的時(shí)候，[i, r] 才是空集。原本的四個(gè)區(qū)間，變成三個(gè)區(qū)間。
注意此時(shí)由于 i > r，實(shí)際上 i = r + 1，那么區(qū)間 (r, length) 就是 [i, length)。 由于最終狀態(tài)是將一個(gè)亂序的數(shù)組切分成三部分，所以這個(gè)方法又叫三路切分。
接下來(lái)我們看一個(gè)例子：
給你一個(gè) 非空 整數(shù)數(shù)組 nums ，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素。 你必須設(shè)計(jì)并實(shí)現(xiàn)線性時(shí)間復(fù)雜度的算法來(lái)解決此問(wèn)題，且該算法只使用常量額外空間。
示例 1 ：輸入：nums = [2,2,1]輸出：1示例 2 ：輸入：nums = [4,1,2,1,2]輸出：4示例 3 ：輸入：nums = [1]輸出：1這道題目想想用“三路切分”如何實(shí)現(xiàn)？
任意選中一個(gè)數(shù)字 x ，將數(shù)組分成三份，那么是不是會(huì)出現(xiàn)三種情況？
通過(guò)分析可知 3 種情況中，只有第二種情況得到了結(jié)果。而第一種情況只出現(xiàn) 1 次的數(shù)在左區(qū)間時(shí)，只需要遞歸地處理左區(qū)間；第三種情況只出現(xiàn) 1 次的數(shù)在右區(qū)間時(shí)，只需要遞歸地處理右區(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)的信息傳遞左右子子樹(shù) // 切分完畢之后，只有三個(gè)區(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)，不過(guò)也不失一種有趣的解法。數(shù)組其實(shí)是另外一種形式的二叉樹(shù)，只不過(guò)有時(shí)候需要我們動(dòng)態(tài)地把左/右子樹(shù)給切分出來(lái)，不同的切分方式，可以解決不同的問(wèn)題。
本文鏈接：http://www.www897cc.com/showinfo-26-12682-0.html你知道“二分”，那你知道“三路切分”嗎？
聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請(qǐng)聯(lián)系：2376512515@qq.com 津ICP備18001702號(hào)
津公網(wǎng)安備 12010102000574號(hào)