输出前K大的数

2019-11-08 03:05:23

字体：大中小

来源：转载

供稿：网友

关于问题

描述

给定一个数组，统计前k大的数并且把这k个数从大到小输出。

输入

第一行包含一个整数n，表示数组的大小。n < 100000。第二行包含n个整数，表示数组的元素，整数之间以一个空格分开。每个整数的绝对值不超过100000000。第三行包含一个整数k。k < n。

输出

从大到小输出前k大的数，每个数一行。

样例输入

10 4 5 6 9 8 7 1 2 3 0 5

样例输出

9 8 7 6 5

解决方法

排序(应用快速排序)后输出，复杂度（nlogn）

分治处理，复杂度（n+klogk）

思路：把前k大的都弄到数组最右边，然后对最右边这k个进行排序输出

关键：在O(n)时间内把前k个都弄到数组最右边

具体实现：

（设数组起始下标为start,结束下边为end,基准元素下标为PRivot） 1.应用快速排序的思想，一趟快速排序后，privot左边的所有元素都<=privot，privot右边的所有元素都>=privot， 2.此时若privot右边的元素个数（end-privot+1）刚好等于K就rerturn 如果右边的元素个数少于K,那么在[start,privot-1]的范围内再找前（k-（end-privot+1））大的数否则就继续在[privot+1,end]的范围内找前k大的数

时间复杂度分析

每次都是选择数组的前部分或者后一部分进行操作，我们在这里假设每次都恰好是一半 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)

代码实现

#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;}

注：部分思想引用于郭炜老师的《程序设计与算法二》

上一篇：find 命令小结

下一篇：用linux进行简单进度条编辑