算法

(DP) $O(n)$

采用动态规划的方法，用一个有序数组dp记录前$n$个丑数。三个指针l2，l3和l5指向dp中的元素，最小的丑数只可能出现在dp[l2]的2倍、dp[l3]的3倍和dp[l5]的5倍三者中间。通过移动三个指针，就能保证生成的丑数是有序的。

• 初始化数组dp和三个指针l2、l3和l5。dp[0] = 1，表示最小的丑数为1。三个指针都指向dp[0]。
• 重复以下步骤$n$次，dp[i]表示第i + 1小的丑数：
  – 比较2 * dp[l2], 3 * dp[l3], 5 * dp[l5]三者大小，令dp[i]为其中的最小值。
  – 如果dp[i] == 2 * dp[l2]，l2指针后移一位。
  – 如果dp[i] == 3 * dp[l3]，l3指针后移一位。
  – 如果dp[i] == 5 * dp[l5]，l5指针后移一位。
• dp[n - 1]即为第$n$小的丑数，返回。

C++ 代码

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n);
        dp[0] = 1;
        int l2 = 0, l3 = 0, l5 = 0;
        for(int i = 1; i < n; ++i) {
            // 生成第i+1小的丑数
            dp[i] = min(min(dp[l2] * 2, dp[l3] * 3), dp[l5] * 5);
            if (dp[i] == dp[l2] * 2) {
                ++l2;
            }
            if (dp[i] == dp[l3] * 3) {
                ++l3;
            } 
            if (dp[i] == dp[l5] * 5) {
                ++l5;
            }
        }
        return dp[n - 1];
    }
};