程序员面试金典--取前K小的数

 

给定 n， k 和 n个不同的数字，取前k小个数。

输入：

7 2

7 9 3 2 12 4 8

输出： 

2 3

 

使用堆排序，可以达到O(n) 的时间复杂度。

 

#include 
     
       const int MAXN = 10000 + 10;int n, k, cnt, num[MAXN], a[MAXN], ans[MAXN]; void AdjustHeap(int x){	int idx = x; 	int lchild = 2*x + 1; 	int rchild = 2*x + 2; 	if(idx < k){		if(lchild < k && a[idx] < a[lchild]){			idx = lchild; 		}		if(rchild < k && a[idx] < a[rchild]){			idx = rchild; 		}		if(idx != x){			int tmp = a[idx]; 			a[idx] = a[x]; 			a[x] = tmp; 			AdjustHeap(idx); 		}	}} int main(){	freopen("in.txt", "r", stdin); 	while(scanf("%d %d", &n, &k) != EOF){		for(int i=0; i
      
       =0; --i){			AdjustHeap(i); 		} 		for(int i=k; i
       
         num[i]){				a[0] = num[i]; 				AdjustHeap(0);			}		}		cnt = 0; 		for(int i=k-1; i>=0; --i){			ans[cnt++] = a[0]; 			a[0] = a[i]; 			AdjustHeap(0); 		}		for(int i=cnt-1; i>0; --i){			printf("%d ",  ans[i]);		}		printf("%d\n", ans[0] );	}	return 0; }