首發公衆号：<code>bigsai</code> ，轉載請附上本文連結
hello，大家好，我是bigsai哥哥，好久不見，甚是想念哇🤩！
今天給大家分享一個TOPK問題，不過我這裡不考慮特别大分布式的解決方案，普通的一道算法題。
首先搞清楚，什麼是topK問題？
topK問題，就是找出序列中前k大(或小)的數，topK問題和第K大(或小)的解題思路其實大緻一緻的。
TopK問題是一個非常經典的問題，在筆試和面試中出現的頻率都非常非常高(從不說假話)。下面，從小小白的出發點,認為topK是求前K大的問題，一起認識下TopK吧！
目前，在求TopK和第K大問題解法差不多，這裡就用力扣215數組的第k個大元素 作為解答的題示範啦。學習topk之前，這篇程式員必知必會的十大排序一定要會。
找到TopK，并且排序TopK
啥，你想要我找到TopK？不光光TopK，你想要多少個，我給你多少個，并且還給你排序給排好，啥排序我最熟悉呢？
如果你想到冒泡排序O(n^2)那你就大意了啊。
如果使用O(n^2)級别的排序算法，那也是要優化的，其中冒泡排序和簡單選擇排序，每一趟都能順序确定一個最大(最小)的值，是以不需要把所有的資料都排序出來，隻需要執行K次就行啦，是以這種算法的時間複雜度也是O(nk)。
這裡給大家回顧一下冒泡排序和簡單選擇排序差別：
冒泡排序和簡單選擇排序都是多趟，每趟都能确定一個最大或者最小，差別就是冒泡在枚舉過程中隻和自己後面比較，如果比後面大那麼就交換；而簡單選擇是每次标記一個最大或者最小的數和位置，然後用這一趟的最後一個位置數和它交換(每一趟确定一個數枚舉範圍都慢慢變小)。
下面用一張圖表示過程：
這裡把code也給大家提供一下，簡單選擇上面圖給的是每次選最小，實作的時候每次選最大就可以了。
當然，快排和歸并排序甚至堆排序也可以啊，這些排序的時間複雜度為O(nlogn),也就是将所有資料排序完然後直接傳回結果，這部分就不再詳細講解啦，調調api或者手寫排序都可。
兩種思路的話除了K極小的情況O(nk)快一些，大部分情況其實還是O(nlogn)情況快一些的，不過從O(n^2)想到O(nk)，還是有所收獲的。
這裡需要知道堆相關的知識，我以前寫過優先隊列和堆排序，這裡先不重複講，大家也可以看一下：
優先隊列不知道，看看堆排序吧
硬核，手寫一個優先隊列
上面說道堆排序O(nlogn)那是将所有元素都排序完然後取前k個，但是其實上我們分析一下這個堆排序的過程和幾個注意點哈：
堆這種資料結構，分為大根堆和小根堆，小根堆是父節點值小于子節點值，大根堆是父節點的值大于子節點的值，這裡肯定是要采用大根堆的。
堆看起來是一個樹形結構，但是堆是個完全二叉樹我們用數組存儲效率非常高，并且也非常容易利用下标直接找到父子節點，是以都用數組來實作堆，每次排序完成的節點都将數移到數組末尾讓一個新數組組成一個新的堆繼續。
堆排序從大的來看可以分成兩個部分，無序數組建堆和在堆基礎上每次取對頂排序。其中無序數組建堆的時間複雜度為O(n),在堆基礎上排序每次取堆頂元素，然後将最後一個元素移到堆頂進行調整堆，每次隻需要O(logn)級别的時間複雜度，完整排序完n次就是O(nlogn)，但是咱們每次隻需要k次，是以完成k個元素排序功能需要花費O(klogn)時間複雜度，整個時間複雜度為O(n+klogn)因為和前面區分一下就不合并了。
畫了一張圖幫助大家了解，進行兩次就獲得Top2，進行k次就獲得TopK了。
實作代碼為：
排序總有一些騷操作的排序—線性排序，那麼你可能會問桶類排序可以嘛？
也可以啦，不過要看數值範圍進行優化，桶類排序适合資料均勻密集出現次數比較多的情況，而計數排序更是希望數值能夠小一點。
那麼利用桶類排序的具體核心思想是怎麼樣的呢？
先用計數排序統計各個數字出現次數，然後将新開一個數組從後往前疊加求和計算。
這種情況非常适合數值巨量并且分布範圍不大的情況。
代碼本來不想寫了，但是念在你會給我三連我寫一下吧
好啦，今天的TopK問題就到這裡啦，相信你下次遇到肯定會拿捏它。
TopK問題不難，就是巧妙利用排序而已。排序是非常重要的，面試會非常高頻。
這裡我就不藏着掖着攤牌了，以面試官的角度會怎麼引導你說TOPK問題。
狡猾的面試官：
嗯，我們來聊聊資料結構與算法，來講講排序吧，你應該接觸過吧？講出你最熟悉的三種排序方式，并講解一下其中具體算法方式。
卑微的我：
bia la bia la bia la bia la……
如果你提到快排，桶排序說不定就讓你用這個排序實作一下TopK問題，其他排序也可能，是以掌握好十大排序是非常必要的！
個人原創公衆号：<code>bigsai</code> 歡迎關注，花了半年寫了一本原創資料結構與算法pdf。