• 欢迎光临~

题解 P1923 【【深基9.例4】求第 k 小的数】

开发技术 开发技术 2022-07-21 次浏览

题解 P1923 【求第 k 小的数】

题目大意:

设计一个平均时间为O(n)的算法,在n(1<=n<=5000000)个无序的整数中找出第k小的数。

题目理解:

因为本题要求使用O(n)的时间,所以不能直接采用排序然后输出的方法来解题。因此采用分治方法,先任意找数组中的一个元素a,采用快速排序将数组进行一次划分,即将小于a的元素放在其左侧,大于a的元素放在其右侧。然后判断元素a是否满足题目为第k小的数,满足则直接输出,否则判断下一次在哪一区间进行划分。

快排:

int quicksort(int left,int right)
{//将数组a的第left到right个元素进行划分
	int mid=a[left];
	while (left<right) 
	{//采用快排策略
		while (left<right&&mid<=a[right])
			right--;
		a[left] = a[right];
		while (left<right&&a[left]<=mid)
			left++;
		a[right] = a[left];
	}
	a[left]=mid;
	return left;
}

查找:

int find(int left, int right, int k)
{	//在数组a的第left到right中寻找第k小的数
	int tem=quicksort(left,right);
	if(k==tem)
		printf("%d",a[k]);
	else if(k-1<tem)//判断下一次划分在哪一区间进行
		find(left,tem-1,k);
	else
		find(tem+1,right,k);
	return 0;
}

由于cin,cout时间过长,所以我在这里用了快读。

用scanf和printf也是可以的

完整代码:

#include<bits/stdc++.h>
using namespace std;
long long a[5000010];//一定要设全局变量 
inline int read(){	//快读 
    char ch=getchar();
	int x=0,f=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    } 
	while('0'<=ch&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    } return x*f;
}
int quicksort(int left,int right)
{
	int mid=a[left];
	while (left<right) 
	{
		while (left<right&&mid<=a[right])
			right--;
		a[left] = a[right];
		while (left<right&&a[left]<=mid)
			left++;
		a[right] = a[left];
	}
	a[left]=mid;
	return left;
}
int find(int left, int right, int k)
{	
	int tem=quicksort(left,right);
	if(k==tem)
		printf("%d",a[k]);
	else if(k-1<tem)
		find(left,tem-1,k);
	else
		find(tem+1,right,k);
	return 0;
}
int main()
{
	int n,k;
	n=read();
	k=read();
	for(int i=0;i<n;i++)
		a[i]=read();
	find(0,n-1,k);
	return 0;
}

此代码已AC,请放心食用。

程序员灯塔
转载请注明原文链接:题解 P1923 【【深基9.例4】求第 k 小的数】
喜欢 (0)