找數組中第K大的數，請教？我們可以考慮泡泡算法，即先按當前大小排列數組中的值，然后輸出K-1st所謂的（第一）K-最大數問題是指在長度為n（n>）的無序數組中，從大到小的順序找到（第一）K個數的問

找數組中第K大的數，請教？

我們可以考慮泡泡算法，即先按當前大小排列數組中的值，然后輸出K-1st

所謂的（第一）K-最大數問題是指在長度為n（n>）的無序數組中，從大到小的順序找到（第一）K個數的問題=k）。

解決方案1：我們可以先將無序數組從大到小排序，然后取出最上面的k，總時間復雜度為O（n*logn k）。

解決方案2：使用選擇排序或交互式排序，可在選擇k次后獲得第k個最大數?？倳r間復雜度為O（n*k）

解決方案3：利用快速排序的思想，從數組s中隨機找到一個元素x，將數組分為SA和sb兩部分。SA中的元素大于或等于x，sb中的元素小于x。在這種情況下，有兩種情況：

1。如果SA中的元素數小于k，則sb中的k-| SA |元素是第k個最大數；

2。如果SA中的元素數大于或等于K，則返回SA中第K個最大的元素數。時間復雜度約為o（n）

解決方案4：二進制[smin，Smax]搜索結果x，統計信息x出現在數組中，整個數組中的k-1數是第k個最大數。平均時間復雜度為O（n*logn）

解決方案5：使用O（4*n）方法為原始數量構建最大堆，然后彈出K次。時間復雜度為O（4*n，K*logn）

解決方案6：保持最小堆大小為K。對于數組中的每個元素，判斷堆頂的大小。如果堆頂很大，則無所謂。否則，彈出堆頂并將當前值插入堆中。時間復雜度O（n*logK）

解決方案7：使用哈希保存數組中元素Si的出現次數，利用計數和排序的思想，在由大到小的線性掃描過程中，前面有k-1的數字是第k個最大的數字，平均時間復雜度O（n）