博客

怎么解决这个问题呢。。

第一思路：直接暴力求解，用希尔排序算法，然后遍历寻找最小整数即可。

1.读取

2.希尔排序

结束

看到有大佬用桶排序和什么主席树的，列入打卡学习目标，不过暂时不需要

这道题就当复习一下昨天学习的希尔排序把！

代码：

#include<stdio.h>
int num[10005]={0},n=0,k=0;
void scan()
{
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&num[i]);
	}
}
void swap(int a,int b)
{
	int tmp;
	tmp=num[a];
	num[a]=num[b];
	num[b]=tmp;
}
void sort()//希尔排序 
{
	int tmp;
	for(int gap=n/2;gap>0;gap=gap/2)
	{
		for(int i=gap+1;i<=n;i++)
		{
			for(int j=i;j-gap>0&&num[j]<num[j-gap];j=j-gap)
			{
				swap(j,j-gap);
			}
		}
	}
}
void print()
{
	int cnt=1,formal;
	formal=num[1];
	for(int i=2;i<=n;i++)
	{
		if(num[i]!=formal)
		{
			formal=num[i];
			cnt++;
			if(cnt==k)
			{
				printf("%d",num[i]);
				return ;
			}
		}
	}
	printf("NO RESULT");
}
int main()
{
	scan();
	sort();
	print();
	return 0;
}