17、数据结构与算法实战:第k小的数

Description
现有一个包含n个整数(1<=n<=900000)的无序序列(保证序列内元素各不相同),输入一个整数k(1<=k<=n),请用较快的方式找出该序列的第k小数并输出。

Input
多组输入。首先输入一个数据组数T(1<=T<=100) 接下来是T组数据。 每组数据有两行。 第一行先输入两个整数,n和k。 接下来是一行输入n个由空格分开的互不相同的整数num(1<=num<=90000000)。

Output
对于每组数据,输出该组数据中第k小的数num。

Sample Input
1
64
325 1 4 6

Sample Output
4

参考程序

#include <stdio.h>
#include <stdlib.h>
#define MAX_LEN 90000

int Split(int a[],int low,int high)
{
   
     
	int temp;
	temp=a[low];
	while(1)
	{
   
     
		while(low<high&&a[high]>=temp)
		{
   
     
			high--;
		}
		if(low==high)
		{
   
     
			break;
		}
		a[low++]=a[high];
		while(low<high&&a[low]<temp)
		{
   
     
			low++;
		}
		if(low==high)
		{
   
     
			break;
		}
		a[high--]=a[low];
	}
	a[low]=temp;
	return low;
}
void Find(int a[],int start,int end,int k)
{
   
     
	int SplitTag=Split(a,start,end);
	if(k-1==SplitTag)
	{
   
     
		printf("%d\n",a[SplitTag]);
	}
	else if(k-1>SplitTag)
	{
   
     
		Find(a,SplitTag+1,end,k);
	}
	else
	{
   
     
		Find(a,start,SplitTag-1,k);
	}
}

int main()
{
   
     
	int T,a[MAX_LEN],n,k,i;
	scanf("%d",&T);
	while(T--)
	{
   
     
		scanf("%d%d",&n,&k);
		for(i=0;i<n;i++)
		{
   
     
			scanf("%d",&a[i]);
		}
		Find(a,0,n-1,k);
	}
	return 0;
}

分析:
本题实现原理是基于“一趟快排”的。因进行一趟快排可以把轴枢元素放在数组中准确的位次上,而且还能是的比轴枢元素大的和比轴枢元素小的分别放在其边。那么如果此轴枢元素的的位置下标正好等于k-1,则输出轴枢元素值;若位置下标小于k-1,则说明第k小的数应位于轴枢元素前边的一半数组中,则递归调用Find函数;同理如果此轴枢元素的位置下标大于k-1,则说明第k小的数应位于轴枢元素后边的一半数组中,继续递归调用Find函数。
类似题目也可参考我写的博客:“数据结构与算法-8数组的分割”,此题是考研真题。

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: