題目：
我們把只包含因子2、3和5的數(shù)稱(chēng)作丑數(shù)（Ugly Number）。求按從小到大的順序的第1500個(gè)丑數(shù)。習(xí)慣上把1當(dāng)做第一個(gè)丑數(shù)

解法一：
判斷一個(gè)數(shù)是否是丑數(shù)：

bool isUglyNumber(int number) {
    while (number % 2 == 0) {
        number /= 2;
    }
    while (number % 3 == 0) {
        number /= 3;
    }
    while (number % 5 == 0) {
        number /= 5;
    }
    return number == 1 ? true : false;
}

那么要求第n個(gè)丑數(shù)，依次迭代即可。

解法二：
思考丑數(shù)是怎么形成的——都是前面已有丑數(shù)乘以2、3或5生成的。假設(shè)已有丑數(shù)已按增序排列，那么下一個(gè)丑數(shù)一定是已有丑數(shù)分別乘以2、3、5得到的數(shù)中大于當(dāng)前最大丑數(shù)中的最小的一個(gè)。優(yōu)化：在乘以2得到的丑數(shù)當(dāng)中有小于當(dāng)前最大丑數(shù)的，也有大于當(dāng)前最大丑數(shù)的，而且一定是某個(gè)點(diǎn)前面的小于，后面的大于，我們只需要那個(gè)點(diǎn)即可。對(duì)于乘以3得到的丑數(shù)、乘以5得到的丑數(shù)同理。

int min(const int a, const int b, const int c) {
    int min = a < b ? a : b;
    return min < c : min :c;
}

int getUglyNumber(int index) {
    vector<int>  uglyNumbers;
    uglyNumbers.push_back(1);
    int cnt = 1;
    int p2 = 0;
    int p3 = 0;
    int p5 = 0;
    while (cnt < index) {
        uglyNumbers.push_back(min(uglyNumbers[p2]*2, uglyNumbers[p3]*3, uglyNumbers[p5]*5));
        ++cnt;
        while (uglyNumbers[p2]*2 <= uglyNumbers[cnt-1]) ++p2;
        while (uglyNumbers[p3]*3 <= uglyNumbers[cnt-1]) ++p3;
        while (uglyNumbers[p5]*5 <= uglyNumbers[cnt-1]) ++p5;
    }
    return uglyNumbers[cnt-1];
}