深入第K大數(shù)問題以及算法概要的詳解
解法1： 我們可以對這個亂序數(shù)組按照從大到小先行排序，然后取出前k大，總的時間復雜度為O(n*logn + k)。
解法2： 利用選擇排序或交互排序，K次選擇后即可得到第k大的數(shù)?？偟臅r間復雜度為O(n*k)
解法3： 利用快速排序的思想，從數(shù)組S中隨機找出一個元素X，把數(shù)組分為兩部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。這時有兩種情況：
1. Sa中元素的個數(shù)小于k，則Sb中的第k-|Sa|個元素即為第k大數(shù)；
2. Sa中元素的個數(shù)大于等于k，則返回Sa中的第k大數(shù)。時間復雜度近似為O(n)
解法4： 二分[Smin,Smax]查找結(jié)果X，統(tǒng)計X在數(shù)組中出現(xiàn)，且整個數(shù)組中比X大的數(shù)目為k-1的數(shù)即為第k大數(shù)。時間復雜度平均情況為O(n*logn)
解法5：用O(4*n)的方法對原數(shù)組建最大堆，然后pop出k次即可。時間復雜度為O(4*n + k*logn)
解法6：維護一個k大小的最小堆，對于數(shù)組中的每一個元素判斷與堆頂?shù)拇笮?，若堆頂較大，則不管，否則，彈出堆頂，將當前值插入到堆中。時間復雜度O(n * logk)
解法7：利用hash保存數(shù)組中元素Si出現(xiàn)的次數(shù)，利用計數(shù)排序的思想，線性從大到小掃描過程中，前面有k-1個數(shù)則為第k大數(shù)，平均情況下時間復雜度O(n)
相關文章
這篇文章主要介紹了C語言字符串轉(zhuǎn)換為Python字符串的方法，文中講解非常細致，代碼幫助大家更好的理解和學習，感興趣的朋友可以了解下2020-07-07
可執(zhí)行體其實也叫可調(diào)用對象，這也是面試常常會考到的問題，這篇文章就來和大家詳細講講C++中的可執(zhí)行體，感興趣的小伙伴可以了解一下2023-06-06
QT線程池的使用(QThreadPool類和QRunnable類)
本文主要介紹了QT線程池的使用(QThreadPool類和QRunnable類)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-04-04
這篇文章主要為大家詳細介紹了OpenCV如何使用BackgroundSubstractor(BSM)實現(xiàn)視頻中移動對象統(tǒng)計功能，文中的示例代碼講解詳細，需要的可以參考一下2023-02-02
函數(shù)就是一段封裝好的，可以重復使用的代碼，它使得我們的程序更加模塊化，不需要編寫大量重復的代碼。這篇文章主要介紹了c語言是如何處理函數(shù)調(diào)用的？需要的朋友可以參考下2023-02-02
VisualStudio2022編寫C語言的實現(xiàn)步驟
VisualStudio2022是一款強大的集成開發(fā)環(huán)境,可以用來編寫C語言程序,本文主要介紹了VisualStudio2022編寫C語言的實現(xiàn)步驟,具有一定的參考價值,感興趣的可以了解一下2024-06-06
這篇文章主要介紹了C++17結(jié)構(gòu)化綁定的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-05-05
C++ opencv實現(xiàn)的把藍底照片轉(zhuǎn)化為白底照片功能完整示例
這篇文章主要介紹了C++ opencv實現(xiàn)的把藍底照片轉(zhuǎn)化為白底照片功能,結(jié)合完整實例形式詳細分析了C++使用opencv模塊進行圖片轉(zhuǎn)換操作的相關實現(xiàn)技巧,需要的朋友可以參考下2019-12-12
這篇文章主要介紹了C++中的5個存儲類的作用,存儲類是管理對象的生存期、鏈接和內(nèi)存位置的類型說明符,需要的朋友可以參考下2016-05-05
C++ 虛函數(shù)與純虛函數(shù)的使用與區(qū)別
本文主要介紹了C++ 虛函數(shù)與純虛函數(shù)的使用與區(qū)別，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08