剑指Offer_33

发表于 | 分类于

题目

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

解题思路

后面的丑数是由前面的丑数乘以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
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index <= 0){
            return 0;
        }
        
        int A[] = new int[index];
        A[0] = 1;
        int j = 0, k = 0, l = 0;
        for(int i = 1; i < index; ++i){
            A[i] = Math.min((Math.min(A[j]*2, A[k]*3)), A[l]*5);
            if(A[i] == A[j]*2){
                ++j;
            }
            if(A[i] == A[k]*3){
                ++k;
            }
            if(A[i] == A[l]*5){
                ++l;
            }
        }
        return A[index-1];
    }
}