[LintCode] 4 丑数Ⅱ

设计一个算法，找出只含素因子2，3，5 的第 n 小的数。

描述

设计一个算法，找出只含素因子2，3，5 的第 n 小的数。

符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

样例

1
2
输入：9
输出：10
1
2
输入：1
输出：1

思路

当前丑数必定是之前某个丑数的2倍、3倍、或者5倍。

初始化丑数数组ugly[0]=1，从第一位开始分别乘以2、3、5得到后续丑数。

注意得到丑数后需要保证数组的大小顺序。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    /**
     * @param n: An integer
     * @return: return a  integer as description.
     */
    int nthUglyNumber(int n) {
        // write your code here
        int ugly[n];
        ugly[0] = 1;
    
        int p2,p3,p5;
        p2=p3=p5=0;
    
        for(int i=1;i<n;i++)
        {
            ugly[i]=min(min(ugly[p2]*2,ugly[p3]*3),min(ugly[p2]*2,ugly[p5]*5));
            if(ugly[i]==ugly[p2]*2)
                ++p2;
            if(ugly[i]==ugly[p3]*3)
                ++p3;
            if(ugly[i]==ugly[p5]*5)
                ++p5;
        }
        
        return ugly[n-1];
    }
};
参考

https://blog.csdn.net/htt789/article/details/79992923

LintCode
Count

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！