Ugly Number II

题目：

Ugly number is a number that only have factors 2, 3 and 5.

Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

分析：

这个题目其实有点像是动态规划，熟悉2进制和编码会比较好做，重点是一个关系：

int temp = min(min(uglyNumArray[c2] x 2, uglyNumArray[c3] x 3), uglyNumArray[c5] x 5);

或者说这个有点像state transission

1 - 000

2 - 100

3 - 010

4 - 200

5 - 001

6 - 110 ...

说到底其实是一个找规律的题目。

解法：

class Solution {
public:
    /*
     * @param n an integer
     * @return the nth prime number as description.
     */
    int nthUglyNumber(int n) {
        // write your code here
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        vector<int> uglyNumArray(n);
        uglyNumArray[0] = 1;
        int c2 = 0;
        int c3 = 0;
        int c5 = 0;

        int uglyNum = 1;
        for (int i = 1; i < n; i++) {
            int temp = min(min(uglyNumArray[c2] * 2, uglyNumArray[c3] * 3), uglyNumArray[c5] * 5);
            if (temp == uglyNumArray[c2] * 2) {
                c2++;
            }
            if (temp == uglyNumArray[c3] * 3) {
                c3++;
            }
            if (temp == uglyNumArray[c5] * 5) {
                c5++;
            }
            uglyNumArray[i] = temp;
            uglyNum = temp;
        }

        return uglyNumArray[n - 1];
    }
};