當前位置：網站首頁>數組中的第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
