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(乘以...