1.题目描述
编写一个程序,找出第
n
个丑数。丑数就是只包含质因数
2, 3, 5
的正整数。示例:
输入: n = 10
输出: 12解释:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12
是前 10 个丑数。说明:
1
是丑数。n
不超过1690。
2.解题思路
剑指offer-【33】
丑数的定义是1或者因子只有2 3 5,可推出丑数=丑数*丑数,假定丑数有序序列为:a1,a2,a3…….an
所以可以将以上序列(a1除外)可以分成3类,必定满足: 包含2的有序丑数序列:2a1, 2a2, 2*a3 …..
包含3的有序丑数序列:3a1, 3a2, 3a3 ….. 包含5的有序丑数序列:5a1, 5a2, 5a3 …..
以上3个序列的个数总数和为n个,而且已知a1 = 1了,将以上三个序列合并成一个有序序列即可
3.代码
1 |
class { |
近期评论