Ugly Number II

https://leetcode.com/problems/ugly-number-ii/description/

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.

Thoughts

找出第n大的只能被2，3或5整除的数。以1为第一个数，问题被自然分成了n步，每步action为对对应的数选择乘2，3还是5。对于任意丑数，它未来都会被乘2，3和5形成新的丑数。因此维持三个指针，分别指向还没有乘2，3和5的元素。每步从三个指针里选，然后++。

Code

class Solution {
public:
    int nthUglyNumber(int n) {
        if (n == 0) return 0;
        int p2 = 0, p3 = 0, p5 = 0;  
        vector<int> dp(n);
        dp[0] = 1;
        for (int i = 1; i < n; ++i) {
            const int r2 = dp[p2] * 2, r3 = dp[p3] * 3, r5 = dp[p5] * 5;
            dp[i] = min(min(r2, r3), r5);
            if (dp[i] == r2) ++p2;
            if (dp[i] == r3) ++p3;
            if (dp[i] == r5) ++p5;
        }
        return dp[n - 1];
    }
};

Analysis

Errors:

1. 不是k2 * 2

2. 也不是fi-1] * 2.

时间复杂度O(n)