面試題—— 找出一個無序整型數組中第k大的數。

題目簡介：

經典面試題： 找出一個無序的整型數組中第k大的數。 函數接口如下： int findKthLargestNum( int A[], int N,  int K)

解法一： 全排序 or 冒泡選擇排序（K趟）

全排序:  最簡單的方法就是對整個數組排序（需要将整個數組裝入記憶體），可以用快速排序和推排序。 （注意： 快排的平均時間複雜度為O（N log N），最壞為O(N^2)； 堆排序的最壞和平均時間複雜度都是O（N* log N）。 總的時間複雜度為 O （N*log  N） + O（K） = O（N*log N）

部分排序： 當K很小時，我們一般希望能夠進行部分排序，這就利用到了 冒泡排序和選擇排序的特性。 我們可以進行K趟 冒泡排序或選擇排序， 就可以找到第K大的數。 最壞時間複雜度O（N*K），空間複雜度O（1）

關于 O（N*logN）的算法和O（N*K）算法那個好，關鍵取決于K與log N的大小，一般K<<N.

解法二： 快排排序思想：

快速排序的需要多次的partition，每一次partition把資料分成兩部分；大于key的數放在一邊，小于key的放在另一邊。 現在我們利用快排思想來解決這個問題， 我們每次partition将資料分為兩部分，較小的資料Sl，  較大的資料Su，我們期望有一次partition可以得到正好Su.size() == K； 或者經過幾次partition，正好找到幾次較大的資料為K個。 對于每一次partition，我們根據較大資料部分Su進行如下操作： 注意： 若Su的元素個數==K，周遊這K個數最小的即為所求；  若Su的元素的個數 <Ｋ，　在Sl中進行partition，找K-Su.length個。 若Su的元素的個數 > K, 對數組中的大數部分進行partition

代碼實作： 對于數組A，大小為N，找到K個最大的數 快排是原地排序，我們每次對于給定數組中的範圍[start,end]進行partition，傳回pivot在A數組中對應的pos。若pos == K-1，表示我們找到了第k個最大的數。 若pos > or < K-1， 則在相應的區域繼續進行partition，知道一個pivot傳回對應pos == K-1。   

詳細代碼如下：

#include <iostream>              #include <cstdio> //包含語言重定向函數freopen的庫              #include <algorithm>              #include <utility>              #include <vector>              using namespace std;                  void printArray(int a[], int n){              for (int i=0; i<n; ++i){              cout<<a[i]<<" ";              }              cout<<endl;              }                      /**              partition2 :              大集 | pivot | 小集              */              int partition2(int A[], int start, int end){              //swap(A[start],A[rand()%(end -start)];              int pivot = A[start];              int ix = start;               int jx = start + 1;              while (jx <= end){              if ( A[jx] > pivot ){ //控制大數在前              swap(A[jx], A[ix++]);              }              ++jx;              }              A[ix] = pivot;              return ix;              }                  /*              找出一個數組中第k大的數              */              int findKthNum(int A[], int N, int K){              int start = 0;              int end = N-1;              int pos;              while ( true ){              pos = partition2(A, start , end);                  if ( pos == K-1 ){              break;              }else if (pos > K-1){              end = pos-1;               }else{              start = pos + 1;              }              }              printArray(A,N);              return A[pos];              }              int *Create(int n){                int *p=new int[n];                int i=0;                for(; i < n; i++){                p[i]= rand()%10;                }                return p;              }                int main(){              int *A = NULL;              int n;              int k;              while(cin>>n){              cin>>k;              A = Create(n);              printArray(A, n);              cout<<findKthNum(A,n,k)<<endl;                  }              return 0;              }           

解法三： 采用二分搜尋的思想：

尋找N個數中最大的K 個數，也可以找出最大K個數中的最小的那個（第Kth大的數），然後在周遊一次N個數選出比Kth數達的所有數，最後再加上Kth數就構成最大的K個數。 假如N個數中最大的數為Vmax，最小的數位Vmin，那麼這個N個數中的K大的數一定在區間[Vmin, Vmax] 之間。那麼，可以在 區間内二分搜尋N個數中的第Kth大的數。二分法根據Vmid的值不斷縮小區間[Vmin, Vmax], 最後 知道[Vmin， Vmax] 僅包含Kth Num;

思路挺好， 整個算法的時間複雜度為O（N*log2（|Vmax-Vmin|）但若N個數的大小是均勻分布的，則時間複雜度O（N*log_2^(N) ）。 注意這個方法僅需要一遍又一遍的周遊整個數組集合，不需要做随機通路，若全部資料不能載入記憶體這個算法可以通過[Vmin, Vmax] 進行資料過濾（每次掃描找findLagerNumCun），待剩餘的資料可以載入記憶體後，可進行記憶體排序，不必在通過讀寫檔案的方式來操縱了（實際應用中，要考慮IO開銷）。

詳細代碼如下：

#include <iostream>              #include <algorithm>              #include <utility>              using namespace std;                  //列印數組              void printArray(int a[], int n){              for (int i=0; i<n; ++i){              cout<<a[i]<<" ";              }              cout<<endl;              }                  //傳回A數組中的數大于等于Vmid值的個數              int findLagerNumCun(int A[], int N, int Vmid) {              int cnt = 0;              for (int i = 0; i < N; ++i) {              if (A[i] >= Vmid) {              ++cnt;              }              }              return cnt;              }                  //查找大小為N的數組A中，第K大的數，并傳回              int findKthNum(int A[], int N, int K) {              if (N <= 0) {              cout << "error" << endl;              return -1;              }              int Vmin = A[0];              int Vmax = A[0];              for (int i=1; i < N; ++i) {              Vmin = min(Vmin, A[i]);              Vmax = max(Vmax, A[i]);              }              while (Vmin < Vmax) {              int Vmid = Vmin + (Vmax - Vmin)/2;               if (Vmin == Vmid) { // Vmax == Vmin +1              break; // 這說明了 大于等于Vmax的數小于K， 大于等于Vmin的數大于K， Vmin即為kth number              // 或者不break， 讓 Vmax = Vmin
              }              int cnt = findLagerNumCun(A, N, Vmid);              if (cnt > K) {              Vmin = Vmid;              } else if (cnt < K){              Vmax = Vmid;              } else {              Vmin = Vmid;              Vmax = Vmid;              }              }              return Vmin;              }                  //随機建立一個大小為n的數組，元素1~9              int *create(int n){                int *p=new int[n];                int i=0;                for(; i < n; i++){                p[i] = rand()%10;                }                return p;              }                int main(){              int *A = NULL;              int n;              cout << "input the size of array A:   ";              while (cin >> n) {              A = create(n);              printArray(A, n);              int k;              cout << "input the kth:   ";              cin >> k;              int kth = findKthNum(A, n, k);              cout<< "kth = " << kth << endl;              sort(A, A+n); //排序一下，用來校驗              printArray(A, n); //注意這裡是升序，倒數第k個即為第k最大值              cout << "input the size of array A:   ";              }              return 0;              }           

解法四： 堆排序

維持一個k個元素的最小堆。用一個優先隊列即可。 時間複雜度O（N * log K)。 代碼略。

解法五：計數排序（若N個數中的種類是已知的）

 尋找N個數中第K大的數，在理論上存線上性算法。不過這個線性算法的常數項比較大，在實際應用中效果有時也不太好。

若數組中的N個數都是[0，MAX) 之間的數（也就是數組A中數的範圍類型都知道的），就可以用count[MAX]來記錄每個整數出現的次數（count[i] 表示整數i在數組A中出現的次數）。我們隻需掃描一遍數組就可以得到count數組，然後就可以找到第K大的數。

參考文獻： http://blog.sina.com.cn/s/blog_54f82cc201013tke.html （補發）