新城已无旧少年


私信TA

用户名:s573877411

访问量:17122

签 名:

人类的悲喜并不相通,我只是觉得他们吵闹.

等  级
排  名 205
经  验 6279
参赛次数 1
文章发表 19
年  龄 20
在职情况 学生
学  校 西安工程大学
专  业 大数据

  自我简介:

静,不是外在无声,而是内心无争

解题思路:

就是利用拆开之后的数字放在哈希表里面然后在哈希表里面找需要的数拆开之后的值是多少,在那个值的第几个位置排着,然后直接找就好了,时间复杂度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就是哈希数组

i123456789
f(i)123456789
arr[f(i)]111111111



i10111213
f(i)1234
arr[f(i)]2222



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


i123456789
arr[i]22
2211111

所以我们要是查找第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;
}


 

0.0分

42 人评分

  评论区

2024-03-28 11:05:53
flag那里看不明白,求讲解
2024-03-12 21:32:51
排序算法确实会超时,我快排得了96f分,还是你这个O(n)的好
2022-10-29 21:33:58
真是个好算法
2022-10-29 21:31:15
emm     
for(i=1;i<=n;i++)                    //计算需要的第m个数在那个哈希区间里面 
    {
        if(m>hash_table[i])
        {
            m-=hash_table[i];  
        }else{
            break; 
        }
    }

 这段是不是改成这样更好?
	for(i=0;i<=max;i++){
		if(m>hstable[i]){
			m-=hstable[i];
		}else break;
	}
2022-05-04 11:33:16
  • «
  • 1
  • »