色哟哟视频在线观看-色哟哟视频在线-色哟哟欧美15最新在线-色哟哟免费在线观看-国产l精品国产亚洲区在线观看-国产l精品国产亚洲区久久

0
  • 聊天消息
  • 系統消息
  • 評論與回復
登錄后你可以
  • 下載海量資料
  • 學習在線課程
  • 觀看技術視頻
  • 寫文章/發帖/加入社區
會員中心
創作中心

完善資料讓更多小伙伴認識你,還能領取20積分哦,立即完善>

3天內不再提示

215.數組中的第K個最大元素(Medium)

算法與數據結構 ? 來源:labuladong ? 作者:labuladong ? 2020-12-02 16:00 ? 次閱讀

讀完本文,可以去力扣解決如下題目:

215.數組中的第 K 個最大元素(Medium)

快速選擇算法是一個非常經典的算法,和快速排序算法是親兄弟。

原始題目很簡單,給你輸入一個無序的數組nums和一個正整數k,讓你計算nums中第k大的元素。

那你肯定說,給nums數組排個序,然后取第k個元素,也就是nums[k-1],不就行了嗎?

當然可以,但是排序時間復雜度是O(NlogN),其中N表示數組nums的長度。

我們就想要第k大的元素,卻給整個數組排序,有點殺雞用牛刀的感覺,所以這里就有一些小技巧了,可以把時間復雜度降低到O(NlogK)甚至是O(N),下面我們就來具體講講。

力扣第 215 題「數組中的第 K 個最大元素」就是一道類似的題目,函數簽名如下:

intfindKthLargest(int[]nums,intk);

只不過題目要求找第k個最大的元素,和我們剛才說的第k大的元素在語義上不太一樣,題目的意思相當于是把nums數組降序排列,然后返回第k個元素。

比如輸入nums = [2,1,5,4], k = 2,算法應該返回 4,因為 4 是nums中第 2 個最大的元素。

這種問題有兩種解法,一種是二叉堆(優先隊列)的解法,另一種就是標題說到的快速選擇算法(Quick Select),我們分別來看。

二叉堆解法

二叉堆的解法比較簡單,實際寫算法題的時候,推薦大家寫這種解法,先直接看代碼吧:

二叉堆(優先隊列)是比較常見的數據結構,可以認為它會自動排序,我們前文 手把手實現二叉堆數據結構 實現過這種結構,我就默認大家熟悉它的特性了。

看代碼應該不難理解,可以把小頂堆pq理解成一個篩子,較大的元素會沉淀下去,較小的元素會浮上來;當堆大小超過k的時候,我們就刪掉堆頂的元素,因為這些元素比較小,而我們想要的是前k個最大元素嘛。當nums中的所有元素都過了一遍之后,篩子里面留下的就是最大的k個元素,而堆頂元素是堆中最小的元素,也就是「第k個最大的元素」。

二叉堆插入和刪除的時間復雜度和堆中的元素個數有關,在這里我們堆的大小不會超過k,所以插入和刪除元素的復雜度是O(logK),再套一層 for 循環,總的時間復雜度就是O(NlogK)。空間復雜度很顯然就是二叉堆的大小,為O(K)。

這個解法算是比較簡單的吧,代碼少也不容易出錯,所以說如果筆試面試中出現類似的問題,建議用這種解法。唯一注意的是,Java 的PriorityQueue默認實現是小頂堆,有的語言的優先隊列可能默認是大頂堆,可能需要做一些調整。

快速選擇算法

快速選擇算法比較巧妙,時間復雜度更低,是快速排序的簡化版,一定要熟悉思路。

我們先從快速排序講起。

快速排序的邏輯是,若要對nums[lo..hi]進行排序,我們先找一個分界點p,通過交換元素使得nums[lo..p-1]都小于等于nums[p],且nums[p+1..hi]都大于nums[p],然后遞歸地去nums[lo..p-1]和nums[p+1..hi]中尋找新的分界點,最后整個數組就被排序了。

快速排序的代碼如下:

關鍵就在于這個分界點索引p的確定,我們畫個圖看下partition函數有什么功效:

索引p左側的元素都比nums[p]小,右側的元素都比nums[p]大,意味著這個元素已經放到了正確的位置上,回顧快速排序的邏輯,遞歸調用會把nums[p]之外的元素也都放到正確的位置上,從而實現整個數組排序,這就是快速排序的核心邏輯。

那么這個partition函數如何實現的呢?看下代碼:

熟悉快速排序邏輯的讀者應該可以理解這段代碼的含義了,這個partition函數細節較多,上述代碼參考《算法4》,是眾多寫法中最漂亮簡潔的一種,所以建議背住,這里就不展開解釋了。

好了,對于快速排序的探討到此結束,我們回到一開始的問題,尋找第k大的元素,和快速排序有什么關系?

注意這段代碼:

intp=partition(nums,lo,hi);

我們剛說了,partition函數會將nums[p]排到正確的位置,使得nums[lo..p-1] < nums[p] < nums[p+1..hi]。

那么我們可以把p和k進行比較,如果p < k說明第k大的元素在nums[p+1..hi]中,如果p > k說明第k大的元素在nums[lo..p-1]中。

所以我們可以復用partition函數來實現這道題目,不過在這之前還是要做一下索引轉化:

題目要求的是「第k個最大元素」,這個元素其實就是nums升序排序后「索引」為len(nums) - k的這個元素。

這樣就可以寫出解法代碼:

這個代碼框架其實非常像我們前文二分搜索框架的代碼,這也是這個算法高效的原因,但是時間復雜度為什么是O(N)呢?按理說類似二分搜索的邏輯,時間復雜度應該一定會出現對數才對呀?

其實這個O(N)的時間復雜度是個均攤復雜度,因為我們的partition函數中需要利用雙指針技巧遍歷nums[lo..hi],那么總共遍歷了多少元素呢?

最好情況下,每次p都恰好是正中間(lo + hi) / 2,那么遍歷的元素總數就是:

N + N/2 + N/4 + N/8 + … + 1

這就是等比數列求和公式嘛,求個極限就等于2N,所以遍歷元素個數為2N,時間復雜度為O(N)。

但我們其實不能保證每次p都是正中間的索引的,最壞情況下p一直都是lo + 1或者一直都是hi - 1,遍歷的元素總數就是:

N + (N - 1) + (N - 2) + … + 1

這就是個等差數列求和,時間復雜度會退化到O(N^2),為了盡可能防止極端情況發生,我們需要在算法開始的時候對nums數組來一次隨機打亂:

前文洗牌算法詳解寫過隨機亂置算法,這里就不展開了。當你加上這段代碼之后,平均時間復雜度就是O(N)了,提交代碼后運行速度大幅提升。

總結一下,快速選擇算法就是快速排序的簡化版,復用了partition函數,快速定位第 k 大的元素。相當于對數組部分排序而不需要完全排序,從而提高算法效率,將平均時間復雜度降到O(N)。

責任編輯:xj

原文標題:快排親兄弟:快速選擇算法詳解

文章出處:【微信公眾號:算法與數據結構】歡迎添加關注!文章轉載請注明出處。

聲明:本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人,不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用,如有內容侵權或者其他違規問題,請聯系本站處理。 舉報投訴
  • 算法
    +關注

    關注

    23

    文章

    4608

    瀏覽量

    92844
  • 代碼
    +關注

    關注

    30

    文章

    4780

    瀏覽量

    68539

原文標題:快排親兄弟:快速選擇算法詳解

文章出處:【微信號:TheAlgorithm,微信公眾號:算法與數據結構】歡迎添加關注!文章轉載請注明出處。

收藏 人收藏

    評論

    相關推薦

    Labivew 實現鼠標在數組中選中元素時,精準的顯示所在位置的行、列值方法

    在項目開發,遇到一布爾的二維數組輸入控件,選中數組元素并索引出行列的操作,試過其他大佬的方法,不是特別精準,,嘗試一下還可以,分享給需要
    發表于 12-21 18:07

    數組的下標為什么可以是負數

    a[3],數組名 a 作為數組元素地址,下標 3 表示從這個地址開始向后移動 3 元素,至于具體是幾個字節,得看什么
    的頭像 發表于 12-20 11:18 ?70次閱讀

    指針數組和二維數組有沒有區別

    。 首先是指針數組 s1。 s1 本身是一維數組數組有三元素,每個
    的頭像 發表于 11-24 11:12 ?143次閱讀

    C語言數組應用計算機導論A6講:數組

    C語言數組應用計算機導論A6講:數組
    發表于 11-20 15:33 ?0次下載

    labview字符串數組轉化為數值數組

    常重要的。LabVIEW支持多種數據類型,包括數值、字符串、數組、簇等。在本例,我們將關注字符串數組和數值數組。 字符串數組 :由一系列字
    的頭像 發表于 09-04 17:47 ?2263次閱讀

    在一.c文件定義一個數組遇到的疑問求解

    的時候沒有指定數組的大小,只是做了初始化,而且這個初始化可以看到,而且自己可以定義初始化的值,并且初始化不同元素個數也可以,那么在其他文件求該數組長度可以辦到嗎,比如下面在一
    發表于 05-14 07:03

    嵌入式零長度數組基本操作方法

    就是一長度為0的數組,也就是說不包含任何元素數組。零長度數組在C99標準引入,并在C11
    的頭像 發表于 05-11 08:49 ?926次閱讀
    嵌入式<b class='flag-5'>中</b>零長度<b class='flag-5'>數組</b>基本操作方法

    深入探索KUKA KRL數組應用

    如果 CHAR 類型數組的所有數組元素都擁有相同的字符串,則不必單獨初始化每個數組元素。忽略右側的數組
    的頭像 發表于 04-18 10:37 ?1230次閱讀
    深入探索KUKA KRL<b class='flag-5'>中</b>的<b class='flag-5'>數組</b>應用

    鴻蒙TypeScript入門學習11天【Array(數組)】

    數組對象是使用單獨的變量名來存儲一系列的值。 數組非常常用。
    的頭像 發表于 04-09 14:38 ?1135次閱讀
    鴻蒙TypeScript入門學習<b class='flag-5'>第</b>11天【Array(<b class='flag-5'>數組</b>)】

    C語言中怎么判斷一整型數組里有多少有效元素

    比如 int a[10]={0,1,2,3},我怎么判斷有效元素個數呢?
    發表于 04-09 08:03

    隨機抽取SV數組的一元素方法實現

    如果想從一關聯數組隨機選取一元素,需要逐個訪問它之前的元素,原因是沒辦法能夠直接訪問到
    的頭像 發表于 03-21 10:11 ?989次閱讀
    隨機抽取SV<b class='flag-5'>數組</b><b class='flag-5'>中</b>的一<b class='flag-5'>個</b><b class='flag-5'>元素</b>方法實現

    請問AD軟件怎么添加不同元素之間的間距規則呢?

    AD軟件提供了某一元素針對其他元素之間的間距規則的設置。
    的頭像 發表于 03-21 09:09 ?1354次閱讀
    請問AD軟件<b class='flag-5'>中</b>怎么添加不同<b class='flag-5'>元素</b>之間的間距規則呢?

    數組和鏈表在內存的區別 數組和鏈表的優缺點

    內存的存儲方式: 數組是一種連續存儲的數據結構,它將元素存儲在相鄰的內存位置。這使得數組的訪問效率高,可以通過下標來直接訪問任何一
    的頭像 發表于 02-21 11:30 ?1024次閱讀

    PHP數組的使用方法!

    如何創建數組、添加/刪除元素、訪問數組元素、遍歷數組以及使用數組方法和函數等等。 首先,我們來看
    的頭像 發表于 01-12 15:11 ?540次閱讀

    labview怎么查數組相同元素的個數

    要查找LabVIEW數組相同元素的個數,可以使用以下步驟: 創建一包含要查找的數值的數組
    的頭像 發表于 12-28 16:42 ?3494次閱讀
    主站蜘蛛池模板: 在线播放成人无码日| 久草国产在线播放| beeg日本高清xxxx| 中文字幕1| 影888午夜理论不卡| 亚洲欧美精品无码大片在线观看| 无码一区国产欧美在线资源| 色偷偷91综合久久噜噜| 人妖操女人| 日韩亚洲中文欧美在线| 日日摸夜夜添夜夜爽出水| 三叶草未满十八岁| 日日夜夜噜噜| 欧美 日韩 亚洲 在线| 麻豆国产精品va在线观看约| 麻豆高清区在线| 女同志videos最新另| 欧美午夜不卡在线观看| 青青视频国产依人在线| 日日操夜夜操狠狠操| xxxxx俄罗斯| 少妇内射兰兰久久| 国产精品观看视频免费完整版 | 香艳69xxxxx有声小说| 亚洲精品国产在线网站| 精品久久久久久无码人妻国产馆 | 成人在线高清不卡免费视频| 三级全黄的视频| 久久国产香蕉视频| 99久久夜色精品国产亚洲AV卜| 年轻的搜子8中字在线观看| 最近的2019中文字幕国语版| 久久青草免费线观最新| 99久久免费精品国产免费| 一边吃奶一边添P好爽故事| 久久这里只有精品1| 福利社的阿姨| 99精品观看| 日韩欧美视频一区二区| 二次元美女扒开内裤喷水| 日韩AV无码一区二区三区不卡毛片|