转载请注明出处：

题目描写叙述：

输入n个整数，找出当中最小的K个数。比如输入4,5,1,6,2,7,3,8这8个数字。则最小的4个数字是1,2,3,4。

输入：

每一个測试案例包含2行：

第一行为2个整数n，k(1<=n，k<=200000)，表示数组的长度。

第二行包含n个整数。表示这n个数，数组中的数的范围是[0,1000 000 000]。

输出：

相应每一个測试案例，输出最小的k个数。并按从小到大顺序打印。

例子输入：

8 4

4 5 1 6 2 7 3 8

例子输出：

1 2 3 4

    思路：

    1、最直观的思路依旧是对数组进行高速排序。而后取出前k个元素。这样的时间复杂度为O(nlogn)

    2、这里能够採用相似于的基于Partition的方法，仅仅是这次要求的分界点不是中位数，而是第k小的数，即排序后应该位于数组的第k-1个位置上的元素，这样该分界点前面的k个元素（包含该分界点）便是最小的k个数（这k个数字不一定是排序的）。跟上面那道题目分析的一样，这样的方法的平均时间复杂度为O(n)，最坏情况下的时间复杂度为O(n*n)，一样也能够用算法导论上提出的切割数组的方法。将最坏情况下的时间复杂度控制到O(n)。

    代码例如以下：

#include
     
      #include
      
       #include
       
        void Swap(int *a,int *b){	if(*a != *b)	{		*a = *a + *b;		*b = *a - *b;		*a = *a - *b;	}}/*算法导论版快排的Partition函数*/int Partition(int *A,int low,int high){	if(A==NULL || low<0 || high<0 || low>=high)		return -1;		int small = low-1;	int j;	for(j=low;j
        
          k-1)			index = Random_Partition(A,low,index-1);		else			index = Random_Partition(A,index+1,high);	}}int main(){	int n,k;	while(scanf("%d %d",&n,&k) != EOF)	{		int *A = (int *)malloc(sizeof(int)*n);		if(A == NULL)			exit(EXIT_FAILURE);		int i;		for(i=0;i
        
       
      
     

   

3、能够考虑採用小顶堆，将数组的n个元素建成一个小顶堆，这样最小的元素就位于堆顶，将它与数组的最后一个元素交换。这样最小的元素就保存在了数组的最后一个位置。而后相同利用堆排序的思想。调整前面的n-1个元素，使之再次构成一个小顶堆，这样k次调整后，最小的k个元素便保存在了数组的最后k个位置，并且是从右向左依次增大。

    这样的方法。建立小顶堆须要O(n)的时间，而后筛选出k个最小的数须要对堆调整k次。每次调整所需时间依次为O(logn)、O(log(n-1))、O(log(n-2))...O(log(n-k))。能够近似觉得每次调整须要的时间为O(logn)。这样，该方法的时间复杂度为O(n+klogn)，至于空间复杂度。假设能够改变输入的数组，我们能够直接在数组上建堆和调整堆。这是空间复杂度为O(1)。假设不能改变输入数组的话，我们就要建立一个小顶堆。这样空间复杂度为O(n)。

    我在九度OJ上採用的这样的方法run，结果AC，代码例如以下：

    

#include
     
      #include
      
       /*arr[start+1...end]满足小顶堆的定义，将arr[start]增加到小顶堆arr[start+1...end]中，调整arr[start]的位置，使arr[start...end]也成为小顶堆注：因为数组从0開始计算序号，也就是二叉堆的根节点序号为0，因此序号为i的左右子节点的序号分别为2i+1和2i+2*/void HeapAdjustDown(int *arr,int start,int end){	int temp = arr[start];	//保存当前节点	int i = 2*start+1;		//该节点的左孩子在数组中的位置序号	while(i<=end)	{		//找出左右孩子中最小的那个		if(i+1<=end && arr[i+1]
       
        =temp)				break;		//最小的子节点向上移动，替换掉其父节点		arr[start] = arr[i];		start = i;		i = 2*start+1;	}	arr[start] = temp;}/*得到最小的k个数，保存在arr中的最后面k个位置*/void MinHeapKNum(int *arr,int len,int k){	if(arr==NULL || len<1 || k<1 || k>len)		return;	int i;	//把数组建成为小顶堆	//第一个非叶子节点的位置序号为(len-1)/2	for(i=(len-1)/2;i>=0;i--)		HeapAdjustDown(arr,i,len-1);	//进行堆排序	for(i=len-1;i>=len-k;i--)	{		//堆顶元素和最后一个元素交换位置。		//这样最后的一个位置保存的是最小的数，		//每次循环依次将次小的数值在放进其前面一个位置。		int temp = arr[i];		arr[i] = arr[0];		arr[0] = temp;		//将arr[0...i-1]又一次调整为小顶堆		HeapAdjustDown(arr,0,i-1);	}}int main(){	int n,k;	while(scanf("%d %d",&n,&k) != EOF)	{		int *A = (int *)malloc(sizeof(int)*n);		if(A == NULL)			exit(EXIT_FAILURE);		int i;		for(i=0;i
        
         =n-k;i--)		{			//依据要求的格式输出			if(i == n-k)				printf("%d\n",A[i]);			else				printf("%d ",A[i]);		}	}	return 0;}
        
       
      
     

/**************************************************************

    

Problem: 1371

    

User: mmc_maodun

    

Language: C

    

Result: Accepted

    

Time:840 ms

    

Memory:8752 kb

****************************************************************/

    4、还能够考虑採用大顶堆。但不是用数组的n个元素来建堆。而是用前k个数字来建立大顶堆。而后拿后面的后面的n-k个元素依次与大顶堆中的最大值（即堆顶）元素比較。假设小于该最大元素，则用该元素替换掉堆顶元素。并调整堆使其维持大顶堆的结构，假设大于该最大元素，则直接跳过，继续拿下一个数字与堆顶元素比較。等到全部的元素比較并操作完，这时数组中后面的元素都比该大顶堆中的数字要大。那么该大顶堆中的k各数字变为数组中最小的k个数字，且堆顶元素为这k个最小数组中最大的，因此它又是数组中第k小的数字。

    该算法建立大顶堆须要的时间为O(k),每次调整堆须要的时间为O(logk)。而总共要调整n-k次。因此时间复杂度为

O(k+(n-k)logk)，当k远远小于n时，时间复杂度可近似为O(nlogk)。另外，该算法非常适合海量数据处理，尤其在内存有限。不能一次读入全部的数据时。当n非常大，而k较小时，一次向内存读入k个数据。而后每次能够读入一个进行比較。这对于内存最多可容纳k个数据时便可满足要求。

    5、也能够用数组保存k个数（事实上能够抽象为一个容器，容器选择的不同，对所需时间会有不同的影响），求其最大值。分别与后面的元素比較，利用与第4中方法相似的策略，最后该数组中个保存的便是最小的k个数字。这样的方法的时间复杂度为O(n*k)。

    以上两种思路代码不再给出。

版权声明：本文博主原创文章，博客，未经同意不得转载。