[[440383]]

本文轉(zhuǎn)載自微信公眾號「bigsai」，作者大賽鴿 。轉(zhuǎn)載本文請聯(lián)系bigsai公眾號。

前言

hello，大家好，我是bigsai哥哥，好久不見，甚是想念哇??!

今天給大家分享一個(gè)TOPK問題，不過我這里不考慮特別大分布式的解決方案，普通的一道算法題。

首先搞清楚，什么是topK問題?

topK問題，就是找出序列中前k大(或小)的數(shù)，topK問題和第K大(或小)的解題思路其實(shí)大致一致的。

TopK問題是一個(gè)非常經(jīng)典的問題，在筆試和面試中出現(xiàn)的頻率都非常非常高(從不說假話)。下面，從小小白的出發(fā)點(diǎn),認(rèn)為topK是求前K大的問題，一起認(rèn)識下TopK吧!

當(dāng)前，在求TopK和第K大問題解法差不多，這里就用力扣215數(shù)組的第k個(gè)大元素 作為解答的題演示啦?？梢钥纯催@篇程序員必知必會十大排序非常有助于學(xué)習(xí)!

排序法

找到TopK，并且排序TopK

啥，你想要我找到TopK?不光光TopK，你想要多少個(gè)，我給你多少個(gè)，并且還給你排序給排好，啥排序我最熟悉呢?

如果你想到冒泡排序O(n^2)那你就大意了啊。

如果使用O(n^2)級別的排序算法，那也是要優(yōu)化的，其中冒泡排序和簡單選擇排序，每一趟都能順序確定一個(gè)最大(最小)的值，所以不需要把所有的數(shù)據(jù)都排序出來，只需要執(zhí)行K次就行啦，所以這種算法的時(shí)間復(fù)雜度也是O(nk)。

這里給大家回顧一下冒泡排序和簡單選擇排序區(qū)別：

冒泡排序和簡單選擇排序都是多趟，每趟都能確定一個(gè)最大或者最小，區(qū)別就是冒泡在枚舉過程中只和自己后面比較，如果比后面大那么就交換;而簡單選擇是每次標(biāo)記一個(gè)最大或者最小的數(shù)和位置，然后用這一趟的最后一個(gè)位置數(shù)和它交換(每一趟確定一個(gè)數(shù)枚舉范圍都慢慢變小)。

下面用一張圖表示過程：

這里把code也給大家提供一下，簡單選擇上面圖給的是每次選最小，實(shí)現(xiàn)的時(shí)候每次選最大就可以了。

//交換數(shù)組中兩位置元素 
private void swap(int[] arr, int i, int j) { 
  int temp = arr[i]; 
  arr[i] = arr[j]; 
  arr[j] = temp; 
} 
//冒泡排序?qū)崿F(xiàn) 
public int findKthLargest1(int[] nums, int k) { 
  for(int i=nums.length-1;i>=nums.length-k;i--)//這里也只是k次 
  { 
    for(int j=0;j<i;j++) 
    { 
      if(nums[j]>nums[j+1])//和右側(cè)鄰居比較 
      { 
        swap(nums,j,j+1); 
      } 
    } 
  } 
  return nums[nums.length-k]; 
} 
//簡單選擇實(shí)現(xiàn) 
public int findKthLargest2(int[] nums, int k) { 
  for (int i = 0; i < k; i++) {//這里只需要K次 
    int max = i; // 最小位置 
    for (int j = i + 1; j < nums.length; j++) { 
      if (nums[j] > nums[max]) { 
        max = j; // 更換最小位置 
      } 
    } 
    if (max != i) { 
      swap(nums, i, max); // 與第i個(gè)位置進(jìn)行交換 
    } 
  } 
  return nums[k-1]; 
} 

當(dāng)然，快排和歸并排序甚至堆排序也可以啊，這些排序的時(shí)間復(fù)雜度為O(nlogn),也就是將所有數(shù)據(jù)排序完然后直接返回結(jié)果，這部分就不再詳細(xì)講解啦，調(diào)調(diào)api或者手寫排序都可。

兩種思路的話除了K極小的情況O(nk)快一些，大部分情況其實(shí)還是O(nlogn)情況快一些的，不過從O(n^2)想到O(nk)，還是有所收獲的。

基于堆排優(yōu)化

這里需要知道堆相關(guān)的知識，我以前寫過優(yōu)先隊(duì)列和堆排序，這里先不重復(fù)講，大家也可以看一下：

優(yōu)先隊(duì)列不知道，看看堆排序吧

硬核，手寫一個(gè)優(yōu)先隊(duì)列

上面說道堆排序O(nlogn)那是將所有元素都排序完然后取前k個(gè)，但是其實(shí)上我們分析一下這個(gè)堆排序的過程和幾個(gè)注意點(diǎn)哈：

堆這種數(shù)據(jù)結(jié)構(gòu)，分為大根堆和小根堆，小根堆是父節(jié)點(diǎn)值小于子節(jié)點(diǎn)值，大根堆是父節(jié)點(diǎn)的值大于子節(jié)點(diǎn)的值，這里肯定是要采用大根堆的。

堆看起來是一個(gè)樹形結(jié)構(gòu)，但是堆是個(gè)完全二叉樹我們用數(shù)組存儲效率非常高，并且也非常容易利用下標(biāo)直接找到父子節(jié)點(diǎn)，所以都用數(shù)組來實(shí)現(xiàn)堆，每次排序完成的節(jié)點(diǎn)都將數(shù)移到數(shù)組末尾讓一個(gè)新數(shù)組組成一個(gè)新的堆繼續(xù)。

堆排序從大的來看可以分成兩個(gè)部分，無序數(shù)組建堆和在堆基礎(chǔ)上每次取對頂排序。其中無序數(shù)組建堆的時(shí)間復(fù)雜度為O(n),在堆基礎(chǔ)上排序每次取堆頂元素，然后將最后一個(gè)元素移到堆頂進(jìn)行調(diào)整堆，每次只需要O(logn)級別的時(shí)間復(fù)雜度，完整排序完n次就是O(nlogn)，但是咱們每次只需要k次，所以完成k個(gè)元素排序功能需要花費(fèi)O(klogn)時(shí)間復(fù)雜度，整個(gè)時(shí)間復(fù)雜度為O(n+klogn)因?yàn)楹颓懊鎱^(qū)分一下就不合并了。

畫了一張圖幫助大家理解，進(jìn)行兩次就獲得Top2，進(jìn)行k次就獲得TopK了。

實(shí)現(xiàn)代碼為：

class Solution { 
    private void swap(int[] arr, int i, int j) { 
        int temp = arr[i]; 
        arr[i] = arr[j]; 
        arr[j] = temp; 
    } 
    //下移交換 把當(dāng)前節(jié)點(diǎn)有效變換成一個(gè)堆(大根) 
    public void shiftDown(int arr[],int index,int len)//0 號位置不用 
    { 
        int leftchild=index*2+1;//左孩子 
        int rightchild=index*2+2;//右孩子 
        if(leftchild>=len) 
            return; 
        else if(rightchild<len&&arr[rightchild]>arr[index]&&arr[rightchild]>arr[leftchild])//右孩子在范圍內(nèi)并且應(yīng)該交換 
        { 
            swap(arr, index, rightchild);//交換節(jié)點(diǎn)值 
            shiftDown(arr, rightchild, len);//可能會對孩子節(jié)點(diǎn)的堆有影響，向下重構(gòu) 
        } 
        else if(arr[leftchild]>arr[index])//交換左孩子 
        { 
            swap(arr, index, leftchild); 
            shiftDown(arr, leftchild, len); 
        } 
    } 
    //將數(shù)組創(chuàng)建成堆 
    public void creatHeap(int arr[]) 
    { 
        for(int i=arr.length/2;i>=0;i--) 
        { 
            shiftDown(arr, i,arr.length); 
        } 
    } 
    public int findKthLargest(int nums[],int k) 
    { 
        //step1建堆 
        creatHeap(nums); 
        //step2 進(jìn)行k次取值建堆，每次取堆頂元素放到末尾 
        for(int i=0;i<k;i++) 
        { 
            int team=nums[0]; 
            nums[0]=nums[nums.length-1-i];//刪除堆頂元素，將末尾元素放到堆頂 
            nums[nums.length-1-i]=team; 
            shiftDown(nums, 0, nums.length-i-1);//將這個(gè)堆調(diào)整為合法的大根堆，注意(邏輯上的)長度有變化 
        } 
        return nums[nums.length-k]; 
    } 
} 

基于快排優(yōu)化

上面堆排序都能優(yōu)化，那么快排呢?

快排當(dāng)然能啊，這么牛的事情怎么能少得了我快排呢?

這部分需要堆快排有一定了解和認(rèn)識，前面很久前寫過：圖解手撕冒泡和快排 (后面待優(yōu)化)，快排的核心思想就是：分治 ，每次確定一個(gè)數(shù)字的位置，然后將數(shù)字分成兩個(gè)部分，左側(cè)比它小，右側(cè)比它大，然后遞歸調(diào)用這個(gè)過程。每次調(diào)整的時(shí)間復(fù)雜度為O(n),平均次數(shù)為logn次，所以平均時(shí)間復(fù)雜度為O(nlogn)。

但是這個(gè)和求TopK有什么關(guān)系呢?

我們求TopK，其實(shí)就是求比目標(biāo)數(shù)字大的K個(gè)，我們隨機(jī)選一個(gè)數(shù)字例如上面的5，5的左側(cè)有4個(gè)，右側(cè)有4個(gè)，可能會出現(xiàn)下面幾種情況了：

① 如果k-1等于5右側(cè)數(shù)量，那么說明中間這個(gè)5就是第K個(gè)，它和它的右側(cè)都是TopK。

②如果k-1小于5右側(cè)數(shù)的數(shù)量 ，那么說明TopK全在5的右側(cè)，那么可以直接壓縮空間成右側(cè)繼續(xù)遞歸調(diào)用同樣方法查找。

③ 如果k-1大于5右側(cè)的數(shù)量，那么說明右側(cè)和5全部在TopK中，然后左側(cè)還有(k-包括5右側(cè)數(shù)總數(shù))，此時(shí)搜查范圍壓縮，k也壓縮。舉個(gè)例子，如果k=7 那么5和5右側(cè)已經(jīng)占了5個(gè)數(shù)字一定在Top7中，我們只需要在5左側(cè)找到Top2就行啦。

這樣一來每次數(shù)值都會被壓縮，這里因?yàn)榭炫挪皇峭耆f歸，時(shí)間復(fù)雜度不是O(nlogn)而是O(n)級別(詳細(xì)的可以找一些網(wǎng)上證明)，但是測試樣例有些極端代碼比如給你跟你有序1 2 3 4 5 6…… 找TOP1 就出現(xiàn)比較極端的情況。所以具體時(shí)候會用一個(gè)隨機(jī)數(shù)和第一個(gè)交換一下防止特殊樣例(僅僅為了刷題用的),當(dāng)然我這里為了就不加隨機(jī)交換的啦，并且如果這里要得到的TopK是未排序的。

詳細(xì)邏輯可以看下實(shí)現(xiàn)代碼為：

class Solution { 
    public int findKthLargest(int[] nums, int k) { 
        quickSort(nums,0,nums.length-1,k); 
        return nums[nums.length-k]; 
    } 
    private void quickSort(int[] nums,int start,int end,int k) { 
        if(start>end) 
            return; 
        int left=start; 
        int right=end; 
        int number=nums[start]; 
        while (left<right){ 
            while (number<=nums[right]&&left<right){ 
                right--; 
            } 
            nums[left]=nums[right]; 
            while (number>=nums[left]&&left<right){ 
                left++; 
            } 
            nums[right]=nums[left]; 
        } 
        nums[left]=number; 
        int num=end-left+1; 
        if(num==k)//找到k就終止 
            return; 
        if(num>k){ 
            quickSort(nums,left+1,end,k); 
        }else { 
            quickSort(nums,start,left-1,k-num); 
        } 
    } 
} 

計(jì)數(shù)排序番外篇

排序總有一些騷操作的排序—線性排序，那么你可能會問桶類排序可以嘛?

也可以啦，不過要看數(shù)值范圍進(jìn)行優(yōu)化，桶類排序適合數(shù)據(jù)均勻密集出現(xiàn)次數(shù)比較多的情況，而計(jì)數(shù)排序更是希望數(shù)值能夠小一點(diǎn)。

那么利用桶類排序的具體核心思想是怎么樣的呢?

先用計(jì)數(shù)排序統(tǒng)計(jì)各個(gè)數(shù)字出現(xiàn)次數(shù)，然后將新開一個(gè)數(shù)組從后往前疊加求和計(jì)算。

這種情況非常適合數(shù)值巨量并且分布范圍不大的情況。

代碼本來不想寫了，但是念在你會給我三連我寫一下吧

//力扣215 
//1 <= k <= nums.length <= 104 
//-104 <= nums[i] <= 104 
public int findKthLargest(int nums[],int k) 
{ 
  int arr[]=new int[20001]; 
  int sum[]=new int[20001]; 
 
  for(int num:nums){ 
    arr[num+10000]++; 
  } 
  for(int i=20000-1;i>=0;i--){ 
    sum[i]+=sum[i+1]+arr[i]; 
    if(sum[i]>=k) 
      return i-10000; 
  } 
  return 0; 
} 

結(jié)語

好啦，今天的TopK問題就到這里啦，相信你下次遇到肯定會拿捏它。

TopK問題不難，就是巧妙利用排序而已。排序是非常重要的，面試會非常高頻。

這里我就不藏著掖著攤牌了，以面試官的角度會怎么引導(dǎo)你說TOPK問題。

狡猾的面試官：

嗯，我們來聊聊數(shù)據(jù)結(jié)構(gòu)與算法，來講講排序吧，你應(yīng)該接觸過吧?講出你最熟悉的三種排序方式，并講解一下其中具體算法方式。

卑微的我：

bia la bia la bia la bia la……