參考博客：傳送門

在上面的博客中介紹了求序列第K大的幾種算法，感覺收益良多，其中最精巧的還是利用快速排序的思想O(n)查詢的算法。仔細學習以后我將其中的幾個實現了一下。

解法 1：

將亂序數組從大到小進行排序然后取出前K大，總的時間復雜度為O(nlogn)

解法 2：

利用選擇排序或交互排序，取出前K大，總的時間復雜度為O(nk)

解法 3：

借鑒快速排序的思想，復雜度近似為O(n)

#include<cstdio> #include<algorithm> #include<cstdlib> using namespace std;int kth_number(int *a,int l,int r,int k) {if(r-l == 1) return a[l];int key=a[l];int index=l;for(int i=l+1;i<r;++i){if(a[i]>=key) continue;else{++index;swap(a[i],a[index]);}}swap(a[index],a[l]);if(r-index == k) return a[index];if(r-index-1 >= k) return kth_number(a,index+1,r,k);else return kth_number(a,l,index,k-r+index); }

測試程序

#include<cstdio> #include"Kth_number.h"using namespace std;int main() {int n,k;const int MAXN=1005;int a[MAXN];printf("n="); scanf("%d",&n);printf("k="); scanf("%d",&k);if(k>n) k=n;printf("please input %d number:\n",n);for(int i=0;i<n;++i)scanf("%d",&a[i]);printf("the %dth number of array is %d\n",k,kth_number(a,0,n,k));return 0; }

運行結果

解法 4：

借助堆排序的思想，將前K個數字彈出，復雜度為建立堆的O(4n)加上k次堆排序O(logn)為O(4n+klogn)

實現程序

#include<cstdio> #include<cstdlib> #include<climits> #include<algorithm> #include<sys/types.h> #include<sys/wait.h> #include<fcntl.h> #include<unistd.h>using namespace std;void Adjust(int *a, int n, int i) {int x = a[i];for(int k = i<<1; k <= n; k = k<<1){if(k+1 <= n && a[k] < a[k+1])++k;if(a[k] > x){a[i] = a[k];i = k;}else{break;}}a[i] = x; }void MakeHeap(int *a, int n) {for(int i = n/2;i > 0;--i){Adjust(a, n, i);} }void HeapSort(int *a,int n,int k,int *ans) {int m=n-k;for(int i = n; i > m; i--){swap(a[1], a[i]);Adjust(a, i-1, 1);}*ans = a[m+1]; }int main(int argc, char* argv[]) {int n;const int MAXN = 1024;scanf("%d", &n);int a[MAXN] = {0};for(int i = 1; i <= n; ++i){scanf("%d", &a[i]);}int k;scanf("%d", &k);if(k > n) k = n;MakeHeap(a, n);int ans;HeapSort(a, n, k, &ans);printf("ans=%d\n", ans);return 0; }

測試結果

解法 5：

維護一個大小為k的小頂堆，對于數組中的每一個元素判斷與堆頂的大小，若堆頂較大，則不管，否則彈出堆頂，將當前值插入到堆中。時間復雜度O(4k+nlogk)

實現程序

#include<cstdio> #include<cstring>using namespace std;void Adjust(int *a,int n,int i) {int x=a[i];for(int k=i<<1;k<=n;k<<=1){if(k+1<=n && a[k]>a[k+1])++k;if(a[k]<x){a[i]=a[k];i=k;}else break;}a[i]=x; } void MakeHeap(int *a,int n) {for(int i=n/2;i>0;--i){Adjust(a,n,i);} } int KthNumber(int *a,int n,int k) { // int *b=new int[k];int b[1024];for(int i=1;i<=k;++i){b[i]=a[i];}MakeHeap(b,k);for(int i=k+1;i<=n;++i){if(a[i]>b[1]){b[1]=a[i];Adjust(b,k,1);}}return b[1]; }int main() {int n,k;printf("n="); scanf("%d",&n);printf("k="); scanf("%d",&k); // int* a = new int[n];int a[1024]={0};for(int i=1;i<=n;++i)scanf("%d",&a[i]);printf("%d\n",KthNumber(a,n,k)); // delete a;return 0; }

測試結果

解法 6:

利用Hash保存數組中元素出現的次數，利用計數排序的思想，線性從大到小掃描中得到結果，時間復雜度為O(n)

總結

以上是生活随笔為你收集整理的求序列第K大算法总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。