當前位置:網站首頁>數組中的第k個最大的元素--優先級隊列、排序、堆、排序

數組中的第k個最大的元素--優先級隊列、排序、堆、排序

2022-01-27 16:33:28 入木

在這裏插入圖片描述

  • 第一大的是6,第二大的是5,所以輸出5

方法1:排序–時間複雜度不好

O(N*logN)–底層是快排

  • 昇序

在這裏插入圖片描述

  • 降序
    在這裏插入圖片描述
    或者
    在這裏插入圖片描述

方法2:優先級隊列–空間複雜度不好

O(N+klogN)–建堆為N,每次出數據向下調為logN,出k次為klogN
空間複雜度為O(N)–k個數大堆底層要存儲
在這裏插入圖片描述

方法3–最優方法

*時間複雜度:O(K+(N-k)logK)–建立k個數的小堆,N-K個數進行pop和push再調整k個數的小堆
空間複雜度:O(k)–建立k個數的小堆
當N遠大於K時,這種方法更有。尤其是N大到內存中存不下必須使用這種方法,前兩個方法用不了,因為第三種只需要存儲k個數
加粗樣式

在這裏插入圖片描述

版權聲明
本文為[入木]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201271633275295.html

隨機推薦