Leetcode 264

题目要求

丑数定义：质因子只有2, 3, 5的数。1为第一个丑数，求第n个丑数

核心算法和原理

• 注意到丑数有个递推性质：若x为丑数，则x * 2, x * 3和x * 5都是丑数

• 由于要求有序，则需要用一个序偶关系维护生成的丑数序列

• 优先队列做法：用小顶堆装生成的丑数，每次取堆顶然后pop，并把堆顶 *2, 3, 5的结果装到小根堆里，计数器+1，直至取出第n个丑数
• 时间：O(nlogn)，空间：O(n)

• N指针做法：对丑数序列，用三个指针进行遍历。初始化指向开头，然后将min(seq[p1] * 2, seq[p2] * 3, seq[p3] * 5) 加到序列末尾，并把argmin_ptr(…)++
• 时间：O(n)，空间：O(n)

代码

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

            dp[i] = min(dp[p1] * 2, min(dp[p2] * 3, dp[p3] * 5));
        }
        return dp[n - 1];
        
    }
};