Medium

题目描述

丑数是只包含质因数 2、3 和 5 的正整数。

给定一个整数 n，返回第 n 个丑数。

示例 1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是前 10 个丑数的序列。

示例 2：

输入：n = 1
输出：1
解释：1 没有质因数，因此它的所有质因数都限制在 2、3 和 5 以内。

约束条件：

  • 1 <= n <= 1690

提示：

  • 朴素方法是对每个数字调用 isUgly，直到找到第 n 个。大部分数字都不是丑数。尝试专注于只生成丑数。
  • 丑数必须由较小的丑数乘以 2、3 或 5 得到。
  • 关键是如何维持丑数的顺序。尝试类似于合并三个有序列表的方法：L₁、L₂ 和 L₃。
  • 假设你有第 k 个丑数 Uₖ，那么 Uₖ₊₁ 必须是 Min(L₁ * 2, L₂ * 3, L₃ * 5)。

解题思路

解题思路

这道题有两种主要解法：三指针动态规划（推荐）和最小堆。

方法一：三指针动态规划（推荐）

核心思想是：每个丑数都可以由之前的丑数乘以 2、3 或 5 得到。我们维护三个指针分别指向可以乘以 2、3、5 的丑数位置。

算法流程：

  1. 初始化 dp 数组，dp[0] = 1（第一个丑数）
  2. 维护三个指针 p2、p3、p5，分别表示下一个要乘以 2、3、5 的丑数的索引
  3. 每次计算 dp[p2] * 2、dp[p3] * 3、dp[p5] * 5 的最小值作为下一个丑数
  4. 更新对应的指针（注意可能有重复值，需要同时更新多个指针）

方法二：最小堆

使用最小堆存储所有可能的丑数，每次取出最小值，然后将其乘以 2、3、5 后加入堆中。需要用集合去重。

三指针方法时间复杂度更优，且空间使用更少，是推荐解法。

代码实现

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

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp = [0] * n
        dp[0] = 1
        
        p2 = p3 = p5 = 0
        
        for i in range(1, n):
            next2 = dp[p2] * 2
            next3 = dp[p3] * 3
            next5 = dp[p5] * 5
            
            dp[i] = min(next2, next3, next5)
            
            if dp[i] == next2:
                p2 += 1
            if dp[i] == next3:
                p3 += 1
            if dp[i] == next5:
                p5 += 1
        
        return dp[n - 1]

public class Solution {
    public int NthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        
        int p2 = 0, p3 = 0, p5 = 0;
        
        for (int i = 1; i < n; i++) {
            int next2 = dp[p2] * 2;
            int next3 = dp[p3] * 3;
            int next5 = dp[p5] * 5;
            
            dp[i] = Math.Min(Math.Min(next2, next3), next5);
            
            if (dp[i] == next2) p2++;
            if (dp[i] == next3) p3++;
            if (dp[i] == next5) p5++;
        }
        
        return dp[n - 1];
    }
}

var nthUglyNumber = function(n) {
    const dp = new Array(n);
    dp[0] = 1;
    
    let p2 = 0, p3 = 0, p5 = 0;
    
    for (let i = 1; i < n; i++) {
        const next2 = dp[p2] * 2;
        const next3 = dp[p3] * 3;
        const next5 = dp[p5] * 5;
        
        dp[i] = Math.min(next2, next3, next5);
        
        if (dp[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型三指针动态规划最小堆方法
时间复杂度O(n)O(n log n)
空间复杂度O(n)O(n)

相关题目