【剑指offer】最小的k的数量

转载请注明出处：http://blog.csdn.net/ns_code/article/details/26966159

题目描写叙述：

输入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<stdio.h>
#include<stdlib.h>
#include<time.h>

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<high;j++)
	{
		if(A[j] <= A[high])
		{
			++small;
			if(j != small)
				Swap(&A[j],&A[small]);
		}
	}
	++small;
	Swap(&A[small],&A[high]);
	return small;
}

int Random_Partition(int *A,int low,int high)
{
	//设置随机种子
	srand((unsigned)time(0));
	int index = low + rand()%(high-low+1);
	Swap(&A[index],&A[high]);
	return Partition(A,low,high);
}

 
/*
返回数组A中出现次数超过一半的数字
基于Partition函数的实现
*/
void MinKNum(int *A,int len,int k)
{
	if(A==NULL || len<1)
		return;

	int low = 0;
	int high = len-1;
	int index = Random_Partition(A,low,high);
	while(index != k-1)
	{
		if(index > 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<n;i++)
			scanf("%d",A+i);

		MinKNum(A,n,k);
		for(i=0;i<k;i++)
		{
			printf("%d ",A[i]);
		}
		printf("
");
	}
	return 0;
}

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<stdio.h>
#include<stdlib.h>

/*
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]<arr[i])  
			i++;
		//假设符合堆的定义，则不用调整位置
		if(arr[i]>=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;i++)
			scanf("%d",A+i);

		MinHeapKNum(A,n,k);
		for(i=n-1;i>=n-k;i--)
		{
			//依据要求的格式输出
			if(i == n-k)
				printf("%d
",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)。

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