一、原題

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

二、題意

定義丑數(shù)：因子只由2、3、5組成的正整數(shù)，例如前十個(gè)丑數(shù)為：1, 2, 3, 4, 5, 6, 8, 9, 10, 12。問如何找出第n個(gè)丑數(shù)。

三、思路

如果寫出下面這個(gè)判斷丑數(shù)的函數(shù)來判斷每一個(gè)數(shù)是不是丑數(shù)，則最大的問題就是每個(gè)整數(shù)都需要計(jì)算，包括一個(gè)不是丑數(shù)的數(shù)字，而且需要重復(fù)求余和除法，算法時(shí)間效率不高。

bool isUgly(int num){
    while(num % 2 == 0){
        num /= 2;
    }
    while(num % 3 == 0){
        num /= 3;
    }
    while(num % 5 == 0){
        num /= 5;
    }
    return num == 1;
}

前面的方法效率之所以低是因?yàn)椴还芤粋€(gè)數(shù)是不是丑數(shù)都要判斷一遍。我們可以考慮找到一種計(jì)算丑數(shù)的方法，而不在非丑數(shù)的整數(shù)上花費(fèi)時(shí)間即可。根據(jù)丑數(shù)的定義，丑數(shù)應(yīng)該是另一個(gè)丑數(shù)乘以2、3或5（1除外），所以可以創(chuàng)建數(shù)組保存已經(jīng)找到的丑數(shù)，后面的丑數(shù)都是前面的某一個(gè)丑數(shù)乘以2、3或5的結(jié)果。

可以通過創(chuàng)建數(shù)組來保存已排好序的丑數(shù)，假設(shè)數(shù)組中已經(jīng)有若干排好序的丑數(shù)，并把最大的丑數(shù)記為M，則分析如何生成下一個(gè)丑數(shù)：

1. 假設(shè)數(shù)組中已經(jīng)有若干個(gè)丑數(shù)已經(jīng)排好序存放在數(shù)組中，并把已有最大的丑數(shù)記為M；
2. 下一個(gè)丑數(shù)肯定是前面某一個(gè)丑數(shù)乘以2、3、5的結(jié)果；
3. 先考慮把已有的每個(gè)丑數(shù)乘以2，在乘以2的時(shí)候，能得到若干個(gè)小于或等于M的結(jié)果，由于是按照順序生成的，小于或等于M的已經(jīng)在數(shù)組中了，不許再考慮；而得到若干個(gè)大于M的結(jié)果，我們只需要第一個(gè)大于M的結(jié)果，因?yàn)槲覀兿Ｍ髷?shù)是按從小到大的順序生成的，其他更大的結(jié)果以后再說。
4. 把第一個(gè)乘以2后大于M的結(jié)果記為M2，同樣，把以后的每個(gè)丑數(shù)乘以3和5，能得到第一個(gè)大于M的結(jié)果M3和M5，那么下一個(gè)丑數(shù)應(yīng)該是M2、M3、M5這三個(gè)數(shù)的最小值；
5. 以上過程把以后的每個(gè)丑數(shù)乘以2、3、5，事實(shí)上并不是必須的，因?yàn)橐延械某髷?shù)是按順序存放在數(shù)組中的。對(duì)乘以2而言，肯定存在某一個(gè)丑數(shù)T2，排在它之前的每一個(gè)丑數(shù)乘以2得到的結(jié)果都會(huì)小于已有的最大丑數(shù)；在它之后的每一個(gè)丑數(shù)乘以2得到的結(jié)果都會(huì)太大，只需要記下這個(gè)丑數(shù)的位置，同時(shí)每次生成新的丑數(shù)的時(shí)候，去更新這個(gè)T2，對(duì)于3、5而言，也存在同樣的T3和T5。
6. 使用p2來記錄T2的坐標(biāo)，p3記錄T3的坐標(biāo)，p5記錄T5的坐標(biāo)，初始狀態(tài)p2=p3=p5=0，p2、p3和p5依次遞增指向前面已排好序的丑數(shù)。

四、代碼

class Solution {
public:
    int min(int a, int b, int c){
        int m = a < b ? a : b;
        return m < c ? m : c;
    }
    
    int nthUglyNumber(int n) {
        if(n == 1) return 1;
        int *dp = new int[n + 1];
        dp[0] = 1;
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;
        for(int i = 1; i <= n; ++i){
            dp[i] = min(2 * dp[p2], 3*dp[p3], 5*dp[p5]);
            if(2 * dp[p2] == dp[i]){
                p2++;
            }
            if(3 * dp[p3] == dp[i]){
                p3++;
            }
            if(5 * dp[p5] == dp[i]){
                p5++;
            }
        }
        int res = dp[n - 1];
        delete[] dp;
        return res;
    }    
};