深入第K大數(shù)問題以及算法概要的詳解
解法1： 我們可以對(duì)這個(gè)亂序數(shù)組按照從大到小先行排序，然后取出前k大，總的時(shí)間復(fù)雜度為O(n*logn + k)。
解法2： 利用選擇排序或交互排序，K次選擇后即可得到第k大的數(shù)?？偟臅r(shí)間復(fù)雜度為O(n*k)
解法3： 利用快速排序的思想，從數(shù)組S中隨機(jī)找出一個(gè)元素X，把數(shù)組分為兩部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。這時(shí)有兩種情況：
1. Sa中元素的個(gè)數(shù)小于k，則Sb中的第k-|Sa|個(gè)元素即為第k大數(shù)；
2. Sa中元素的個(gè)數(shù)大于等于k，則返回Sa中的第k大數(shù)。時(shí)間復(fù)雜度近似為O(n)
解法4： 二分[Smin,Smax]查找結(jié)果X，統(tǒng)計(jì)X在數(shù)組中出現(xiàn)，且整個(gè)數(shù)組中比X大的數(shù)目為k-1的數(shù)即為第k大數(shù)。時(shí)間復(fù)雜度平均情況為O(n*logn)
解法5：用O(4*n)的方法對(duì)原數(shù)組建最大堆，然后pop出k次即可。時(shí)間復(fù)雜度為O(4*n + k*logn)
解法6：維護(hù)一個(gè)k大小的最小堆，對(duì)于數(shù)組中的每一個(gè)元素判斷與堆頂?shù)拇笮?，若堆頂較大，則不管，否則，彈出堆頂，將當(dāng)前值插入到堆中。時(shí)間復(fù)雜度O(n * logk)
解法7：利用hash保存數(shù)組中元素Si出現(xiàn)的次數(shù)，利用計(jì)數(shù)排序的思想，線性從大到小掃描過程中，前面有k-1個(gè)數(shù)則為第k大數(shù)，平均情況下時(shí)間復(fù)雜度O(n)
相關(guān)文章
這篇文章主要介紹了C++?路徑中./、../、/代表的含義，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-12-12
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)日期類的相關(guān)代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-09-09
詳解C++中賦值,關(guān)系,函數(shù)調(diào)用運(yùn)算符重載的實(shí)現(xiàn)
本文主要為大家講解一下三個(gè)C++中的運(yùn)算符重載，分別是賦值運(yùn)算符重載、關(guān)系運(yùn)算符重載和函數(shù)調(diào)用運(yùn)算符重載，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2022-06-06
這篇文章主要介紹了c++模擬實(shí)現(xiàn)string類詳情，string表示可變長(zhǎng)的字符序列，使用string類型必須首先包含string頭文件。作為標(biāo)準(zhǔn)庫(kù)的一部分，string定義在命名空間std中，下面進(jìn)入文章一起看看詳細(xì)內(nèi)容吧2022-01-01
__stdcall 和 __cdecl 的區(qū)別淺析，需要的朋友可以參考一下2013-03-03
C語言數(shù)據(jù)（整數(shù)、浮點(diǎn)數(shù)）在內(nèi)存中的存儲(chǔ)
之前對(duì)c語言數(shù)據(jù)存儲(chǔ)一直不太明白,最近仔細(xì)研究了一番,所以下面這篇文章主要給大家介紹了關(guān)于C語言數(shù)據(jù)（整數(shù)、浮點(diǎn)數(shù)）在內(nèi)存中存儲(chǔ)的相關(guān)資料,需要的朋友可以參考下2021-06-06
這篇文章主要為大家詳細(xì)介紹了基于C語言實(shí)現(xiàn)掃雷游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-11-11
今天小編就為大家分享一篇淺談C語言中的注釋風(fēng)格小結(jié)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-12-12
詳解C++設(shè)計(jì)模式編程中策略模式的優(yōu)缺點(diǎn)及實(shí)現(xiàn)
這篇文章主要介紹了C++設(shè)計(jì)模式編程中策略模式的優(yōu)缺點(diǎn)及實(shí)現(xiàn),文中討論了策略模式中設(shè)計(jì)抽象接口的繼承和組合之間的區(qū)別,需要的朋友可以參考下2016-03-03
這篇文章主要為大家介紹了C++ LeetCode543題解二叉樹直徑，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-12-12