📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 6811| 回复: 28
跳转到指定楼层
上一主题 下一主题
收起左侧

Google : 找丑数

 
全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
包含一个或多个{2,3,5}因子的叫丑数,比如2,4,5,15都是,17不是
找出第n个丑数。

因该有多种方法....

上一篇:Microsoft : Sort 只含0,1,2三个元素的数组
下一篇:google : 计算二进制1的个数
全局:
本帖最后由 wwwyhx 于 2011-4-28 16:49 编辑

每个丑数可以看成是某个丑数和2或3或5相乘的结果,可以建立长度为n的数组a,数组里按从小到大顺序存放前m个丑数,m<n,用三个指针p2,p3,p5标识数组中三个特定位置,使p2前的数乘2都不大于数组中最大的丑数,p3,p5也类似,然后选择*p2*2,*p3*3,*p5*5中最小的丑数插入数组,再如此反复,直到找到第n个丑数。
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-4-28 16:50:09 | 只看该作者
全局:
每个丑数可以看成是某个丑数和2或3或5相乘的结果,可以建立长度为n的数组a,数组里按从小到大顺序存放前m个丑数,m
kidd_yq@163.com 发表于 2011-4-28 15:28



    回复请用白色字体
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-4-28 16:51:57 | 只看该作者
全局:
有没有别的方法???除了标准答案以外
回复

使用道具 举报

🔗
lai 2011-4-28 18:42:48 | 只看该作者
全局:
2 3 5的最大公约数是30,把30以内的丑数穷举出来,假设有k个,大于30的丑数都可以用30以内的丑数加m个30表达,然后求第n丑数就是找用30以内的某个丑数加若干30

感觉我在做算数题,不是算法题。。。
回复

使用道具 举报

全局:
回复 4# wwwyhx

最简单的从2开始穷举,别的方法我还在想会不会有规律,能找出近似的函数表达,再利用估计的值去逼近。。。因为给出指定数再找n要方便的多
回复

使用道具 举报

🔗
Imbalism 2011-4-28 21:27:39 | 只看该作者
全局:
本帖最后由 Imbalism 于 2011-4-28 21:29 编辑

一个bool型的数组a,表示a【i】是否是丑数
a【2】 a【3】 a【5】初始化为true,其它为false
for(i = 2;;i++)
{
    if(a
)
    {
        a[i * 2] = true;
        a[i * 3] = true;
        a[i * 5] = true;
        if(++count == n)
             return i;
    }
}

不知道这样对不对
回复

使用道具 举报

🔗
darksteel 2011-4-29 00:08:30 | 只看该作者
全局:
回复 7# Imbalism
这个思路感觉是可以的,问题在于空间会爆掉。这个题目是poj的1338,查询可以是1500的话,ugly number会达到10位数,就算是bool数组也不行。其实有一种和你方法很类似的是用优先队列,开始放2、3、5进去,然后每次取出队首元素a,把a*2,a*3,a*5放进去。直到取到第n个。这么做会重复放很多数,可以用set代替priority queue。USACO上有一道这个问题的扩展,因子不只是2、3、5,是输入的一串数,在n较大的情况下,这种做法空间也会爆掉,因为就算用set,取到第n个数的时候,其实已经放了非常多更大的数进去,都是无效的。还真只有那个标准做法各个方面都比较稳。
不过这个思路在n比较小的情况下,写起来还是很简练的,看着也很清晰~

   
回复

使用道具 举报

🔗
wwtpcsuper 2011-4-29 06:37:23 | 只看该作者
全局:
本帖最后由 wwtpcsuper 于 2011-4-29 12:48 编辑

我觉得这种题还是从数论角度思考比较好。。。

每30个数里面的丑数是固定的,30是2,3,5的最小公倍数


于是,将{2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30}共17个数存入一个数basic[22]

然后将n%22,丑数就是30*int(n/22)+basic[n%22]

我不说了。。。5楼已经回答了。。。
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-4-29 12:28:19 | 只看该作者
全局:
我觉得这种题还是从数论角度思考比较好。。。

每30个数里面的丑数是固定的,30是2,3,5的最小公倍数

于是,将{2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30}共17个数存入一个数basic[17]

然后将n%17,丑数就是30*int(n/17)+basic[n%17]

我不说了。。。5楼已经回答了。。。
wwtpcsuper 发表于 2011-4-29 06:37


5楼的说法因该是错的,我们deal的是乘数级增加,30的倍数不解决问题
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表