蓝桥杯2022年第十三届省赛真题-重新排序（c语言题解-简单哈希算法,不用排序时间复杂度o(n)）

解题思路:

就是利用拆开之后的数字放在哈希表里面然后在哈希表里面找需要的数拆开之后的值是多少，在那个值的第几个位置排着，然后直接找就好了，时间复杂度o(n),多说一句这个题用排序很可能时间超时了！！！

第一步：

我们先将题目中给的计算方法设置为f(x),先设置哈希函数,由于这个n最大为1000000,所以最大的f(n)就是54(也就是当n=999999),所以数组就可以开到55就行了

那么f算法其实很简单

int f(int x)                  //计算每一个数拆开之后的值 
{
	int sum=0;
	while(x>0)
	{
		sum+=x%10;
		x/=10;
	}
	return sum;
}

第二步:

然后我们来看下怎么利用哈希表来存1-n这些数字,题目要求的是排序好的数然后在求第m个数是多少,我们用哈希表就可以省去排列这个过程,毕竟最快的排序也要nlgn,而我们哈希排法o(n)就可以了,排法就是我们就是将每次的f(x)算出来后直接让arr[f(x)]++就可以了,这样哈希算法就已经从1-55给我们把数组拍好了,我们先看下题目中给的样例是怎么回事的,下面的arr就是哈希数组

所以我们将上面的数组综合一下

所以我们要是查找第5个数,那我们就是找f(x)为3的第一个数就可以了,那用一个for循环找就是3,所以答案就是3

在这里面就有两个步骤先找出在那个区间里面,再去找是该区间的第几个数就好了,至此就完结了!

注意事项:

参考代码:

#include<stdio.h>
#include<string.h>
#define max 55
int hash_table[max];           //定义一个哈希表 
int f(int x)                  //计算每一个数拆开之后的值 
{
	int sum=0;
	while(x>0)
	{
		sum+=x%10;
		x/=10;
	}
	return sum;
}
int main()
{
	memset(hash_table,0,sizeof(hash_table));       //初始化 
	int n,m,i,j,k,flag=0;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)                       //将1-n所有数拆开之后的数放在哈希表里面 
	{
		hash_table[f(i)]++;
	}
	for(i=1;i<=n;i++)                    //计算需要的第m个数在那个哈希区间里面 
	{
		if(m>hash_table[i])
		{
			m-=hash_table[i];	
		}else{
			break;	
		}
	}
	for(j=1;j<=n;j++)                 //从1-n计算直到找到需要的数然后输出 
	{
		if(f(j)==i)
		{
			flag++;
		}
		if(flag==m)
		{
			printf("%d",j);
			break;
		}
	}
	return 0;
}