丑数

题目描述

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

 

思路1：只能被2,3,5整除的就是丑数。

int GetUglyNumber_Solution(int index) {

    if (index <= 0)return -1;

    if (index == 1){
        return 1;
    }
    int num = 2;
    int tmp = 0;
    index -= 1;
    while (index){
        tmp = num;
        while (tmp % 2 == 0){
            tmp /= 2;
        }
        while (tmp % 3 == 0){
            tmp /= 3;
        }
        while (tmp % 5 == 0){
            tmp /= 5;
        }
        if (tmp == 1){
            index--;
            num++;
        }
        else if (tmp>5){
            num++;
        }
    }
    return num-1;
}

思路2：动态规划

//所有丑数都是另一个丑数乘以2，或者乘以3，或者乘以5

//第一个丑数是1，那么我们可以创建一个系列，丑数1*2,1*3,1*5也是丑数

//将1*2,1*3,1*5放入容器vector中，自动按照从小到大排序，

//vector[1]就是第2个最小丑数记做min=2

// min=2, 再将min*2,1*3,1*5,，min=3

// min=3, 2*2,1*3,1*5，min=4

丑数是在之前的某一个丑数的基础上的最小丑数，因此只要记录当前的丑数，是在某一个丑数的基础上，乘以因子2，因子3，因子5。求得最小，就是下一个丑数。

int GetUglyNumber_Solution(int index) {
    if (index <= 0) return 0;
    if (index == 1) return 1;
    vector<int>k(index); k[0] = 1;
    int t2 = 0, t3 = 0, t5 = 0;
    for (int i = 1; i<index; i++) {
        k[i] = min(k[t2] * 2, min(k[t3] * 3, k[t5] * 5));
        if (k[i] == k[t2] * 2) t2++;
        if (k[i] == k[t3] * 3) t3++;
        if (k[i] == k[t5] * 5) t5++;
    }
    return k[index - 1];
}