1. 從快排partition程序借鑒而來，利用partion程序每次能確定一個元素位置來實作，
此演算法期望時間復雜度為O(N)，最差為O(N^2)，
每次確定了一個元素位置后，就能判斷待查的topk個元素是在哪個磁區，只需要遞回一個磁區即可，
代碼如下：
int quickSelect(vector<int>&, int, int, int); int findKthSmallest(vector<int>& arrs, int k) { int sz = arrs.size(); if (k > sz) return -1; return quickSelect(arrs, k, 0, sz - 1); } int quickSelect(vector<int>& arrs, int k, int l, int r) { //選pivot為最右邊那個 更好的方式是隨機選一個 //int pivot = arrs[r]; int random_idx = rand() % (r-l+1) + l; swap(arrs[random_idx], arrs[r]); //int pivot = arrs[r]; // partition程序 int pivot = arrs[r]; int i = l - 1; for (int j = l; j < r; ++j) { //維護一個<= > ?三個區域 if (arrs[j] <= pivot) { swap(arrs[++i], arrs[j]); } } swap(arrs[i+1], arrs[r]); //i+1為最后中軸所在的位置 //遞回程序 if (k == (i+1)) { return arrs[i+1]; } else if (k < (i+1)) { return quickSelect(arrs, k, l, i); } else { return quickSelect(arrs, k, i+2, r); } }
2. 利用堆來實作TOP-K問題
維護一個包含K個元素的堆，求第K大的維護小根堆，求第K小的維護大根堆，
時間復雜度為：O(nlogk)，
代碼如下：
//建堆 + 拔尖 + 調整 void adjustHeap(vector<int>& arr, int i, int len); int findKthSmallest(vector<int>& nums, int k) { //建立一個大頂堆 vector<int> arr(k, 0); for (int i = 0; i < k; ++i) { arr[i] = nums[i]; } for (int i = arr.size() / 2; i >= 0; --i) { adjustHeap(arr, i, arr.size()); } for (int i = k; i < nums.size(); ++i) { if (nums[i] >= arr[0]) continue; arr[0] = nums[i]; adjustHeap(arr, 0, arr.size()); } return arr[0]; }
//調整 void adjustHeap(vector<int>& arr, int i, int len) { int tmp = arr[i]; for (int k = 2*i+1; k < len; k = k*2+1) { if (k < len-1 && arr[k] <= arr[k+1]) k++; if (arr[k] > tmp) { arr[i] = arr[k]; i = k; } else break; } arr[i] = tmp; }
以上是常用的兩種解法，另外：
復雜度更高的解法有：
- 冒泡，時間復雜度O(KN)或者O((N-K)N)，考慮K與n/2的大小；
- 直接用別的排序手段全排序，如歸并，O(NlogN)，
復雜度更低的解法：
- BFPRT演算法，分5組，每組取中位數，可以每次篩選掉更多的元素，時間復雜度嚴格的O(N)，
其他的變種，大檔案中具有超大規模數，求TOP-K：
- 可以采用分治演算法，結合哈希演算法來分到不同檔案，每個小檔案進行TOP-K處理，再進行合并，類似Map-Reduce程序，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/501457.html
標籤：其他