關(guān)于問題
描述
給定一個(gè)數(shù)組，統(tǒng)計(jì)前k大的數(shù)并且把這k個(gè)數(shù)從大到小輸出。
輸入
第一行包含一個(gè)整數(shù)n，表示數(shù)組的大小。n < 100000。 第二行包含n個(gè)整數(shù)，表示數(shù)組的元素，整數(shù)之間以一個(gè)空格分開。每個(gè)整數(shù)的絕對(duì)值不超過100000000。 第三行包含一個(gè)整數(shù)k。k < n。
輸出
從大到小輸出前k大的數(shù)，每個(gè)數(shù)一行。
樣例輸入
10 4 5 6 9 8 7 1 2 3 0 5
樣例輸出
9 8 7 6 5
解決方法
排序(應(yīng)用快速排序)后輸出，復(fù)雜度（nlogn）
分治處理，復(fù)雜度（n+klogk）
思路：把前k大的都弄到數(shù)組最右邊，然后對(duì)最右邊這k個(gè)進(jìn)行排序輸出
關(guān)鍵：在O(n)時(shí)間內(nèi)把前k個(gè)都弄到數(shù)組最右邊
具體實(shí)現(xiàn)：
（設(shè)數(shù)組起始下標(biāo)為start,結(jié)束下邊為end,基準(zhǔn)元素下標(biāo)為PRivot） 1.應(yīng)用快速排序的思想，一趟快速排序后，privot左邊的所有元素都<=privot，privot右邊的所有元素都>=privot， 2.此時(shí)若privot右邊的元素個(gè)數(shù)（end-privot+1）剛好等于K就rerturn 如果右邊的元素個(gè)數(shù)少于K,那么在[start,privot-1]的范圍內(nèi)再找前（k-（end-privot+1））大的數(shù) 否則就繼續(xù)在[privot+1,end]的范圍內(nèi)找前k大的數(shù)
時(shí)間復(fù)雜度分析
每次都是選擇數(shù)組的前部分或者后一部分進(jìn)行操作，我們?cè)谶@里假設(shè)每次都恰好是一半 T(n) = T(n/2) + a*n = T(n/4) + a*n/2 + a*n = T(n/8) + a*n/4 + a*n/2 + a*n = … … = T(1) + … …+ a*n/8 + a*n/4 + a*n/2 + a*n < 2*a*n 即 O(n)
代碼實(shí)現(xiàn)
#include<iostream>#include<cstdio>using namespace std;int k;int a[100005];void swap(int & a,int & b){ int tmp; tmp = a; a = b; b = tmp;}void Qsort( int a[], int s, int e ){ if(s >= e) return; int k = a[s]; int i = s,j = e; while (i < j) { while ( j > i && a[j] >= k ) --j; swap( a[i], a[j]); while ( i < j && a[i] <= k ) ++i; swap( a[i], a[j]); } Qsort( a, s, i-1 ); Qsort( a, i+1, e ); }void arrangeRight(int a[],int k,int s,int e){ if(s <= e) { int kk = a[s]; int i = s,j = e; while (i < j) { while ( j > i && a[j] >= kk ) --j; swap( a[i], a[j]); while ( i < j && a[i] <= kk ) ++i; swap( a[i], a[j]); } if(e - i + 1 == k) return; else if(e - i + 1 > k) arrangeRight(a,k,i+1,e); else arrangeRight(a,k-(e-i+1),s,i-1); }} int main(){ int size; scanf("%d",&size); for(int i=0;i < size;++i) scanf("%d",&a[i]); scanf("%d",&k); arrangeRight(a,k,0,size-1); Qsort(a,size-k,size-1); for(int i = size-1;i >= size - k;--i) printf("%d/n",a[i]); return 0;}注：部分思想引用于郭煒老師的《程序設(shè)計(jì)與算法二》
