264. Ugly Number II

Given an integer n, return the nth ugly number.

Ugly number is a positive number whose prime factors only include 2, 3, and/or 5.

 

Example 1:

Input: n = 10
Output: 12
Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.
Example 2:

Input: n = 1
Output: 1
Explanation: 1 is typically treated as an ugly number.
 

Constraints:

1 <= n <= 1690

这题让我们求第N个丑数。

一开始的解法，丑数肯定是由之前的丑数乘以2,3,5获得，所以我们取最小的丑数，然后预先计算出接下来的丑数。不断的取头部最小的丑数计数，直到取到第n个丑数。

这种解法复杂度很高，耗时很长，经过翻阅资料发现，这题也可以用动态规划来求解。

动态规划的核心在于当前解可以依赖于之前的解来获取，有一个递推的公式。

我们要求当前的丑数，那么只要求出之前的丑数乘以2,3,5后能取到的最小的丑数即可。

我们设定3个指针，分别指向第一个元素（1），然后分别对第一个指针乘以2,第二个乘以3,最后一个5,看看能取到的最小的丑数，将其放入当前的位置。

求出来之后，我们需要直到这个是哪一个求到的，不然下一轮循环还会获得该值，所以我们需要把所有等于该丑数的值的指针，向前挪动一位，让其可以获得新的值。这里可能有多个结果会等于该最小丑数，所以可能需要一次性挪动多个指针。

class UglyNumberII : public Solution {
public:
    void Exec() {
        
    }
    int nthUglyNumber(int n) {
        int res = 1, count = 0;
        set<int64_t> nums{res};
        while (count < n) {
            res = *nums.begin();
            nums.erase(res);
            nums.insert({int64_t(res) * 2, int64_t(res) * 3, int64_t(res) * 5});
            count++;
        }
        return res;
    }
    int nthUglyNumberDP(int n) {
        vector<int> dp(n, 1);
        int p2 = 0, p3 = 0, p5 = 0;
        int num = 1;
        while (num < n) {
            int np2 = dp[p2] * 2;
            int np3 = dp[p3] * 3;
            int np5 = dp[p5] * 5;
            if (np2 <= np3 && np2 <= np5) {
                dp[num++] = np2;
            } else if (np3 <= np2 && np3 <= np5) {
                dp[num++] = np3;
            } else {
                dp[num++] = np5;
            }
            if (dp[num - 1] == np2) p2++;
            if (dp[num - 1] == np3) p3++;
            if (dp[num - 1] == np5) p5++;
        }
        return dp[n - 1];
    }
};