lintcode-4 丑数算法

楚天乐 255 0 条

题目

设计一个算法求出第n个只包含因子2,3,5的数。认为1也是丑数
比如输入9,则返回10;输入1,返回1

分析

只包含因子2,3,5,则这个数的形式就是F = (2^x) (3^y) (5^z), 限制条件x,y,z>=0
求出对应x,y,z即可

1th:x=y=z=0, F1 = (2^0) (3^0) (5^0) = 1
2th:x=1,y=z=0, F2 = 2 F1 = 2
3th:x=0,y=1,z=0, F3 = 3
F1 = 3
4th:x=2,y=0,z=0, F4 = 2 F2 = 4
5TH: x=0,y-0,z-1, F5 = 5
F1 = 5

对于第N个丑数,它的x+y+z < N-1
因子2,3,5的数量。

  • 两个2相乘会大于3,因此增加一个2,就要对应增加一个3
  • 一个2,一个3相乘,会大于5,。因此,增加一个2,3就需要替换成5

F1 = 1
迭代1:基底F1=1
F2 = F1 2 = 2(乘以2最小)
F3 = F1
3 = 3(乘以3最小)
F4 = F1 2 2 = 4(乘以2^2最小)
F5 = F1 5 = 5(乘以5最小)
F6 = F1
2 3 = 6(乘以23最小)
F7 = F1 3 3 = 9(乘以3*3最小)

迭代2:基底 = F5=5
F8 = F5 2 = 10(乘以52最小)
F9 = F5 3 = 15(乘以53最小)
F10 = F5 2 2 = 20(乘以522最小)
F11 = F5 5 = 25(乘以55最小)
F12 = F5 2 3 = 30(乘以523最小)
F13 = F5 3 3 = 45(乘以533最小)

迭代3:基底 = F11 = 25

规律总结:

  1. 每轮迭代可以生成6个丑数,下一轮基底选当前迭代中第四个数。
  2. 每轮迭代的基底,对于第k轮迭代,基底为5^(k-1). B1=5^(1-1)=1, B2=5^(2-1)=5, B3=5^(3-1)=25
  3. 第一轮迭代生成F2-f7, 第二轮迭代生成F8-F13。第k轮迭代生成F((k-1)6+2)到F((k-1)6+7)。
  4. 对于第m个丑数,需要几轮迭代?i = ⌊(m-2)/6⌋+1, 向下取整

算法

  1. 对于第n个丑数,通过i = ⌊(m-2)/6⌋+1计算出他的迭代次数
  2. 通过i计算出基底,base = 5^(i-1)
  3. 计算出nth丑数在当前迭代中的偏移位置, 第k轮迭代生成范围F((k-1)6+2)到F((k-1)6+7)

代码

function nthUglyNumber(n){

}

打赏

微信打赏

支付宝打赏



发表我的评论
昵称 (必填)
邮箱 (必填)
网址
执行时间: 46.813011169434 毫秒