lintcode-4 丑数算法

题目

设计一个算法求出第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){

}