丑数 II 图解题解

丑数 II 到底要找第几个什么数

给一个整数 n，返回第 n 个丑数。丑数是只含质因子 2、3、5 的正整数（质因子＝把一个数拆成质数相乘时用到的那些质数），约定 1 是第 1 个。从小到大数，跳过像 7 这种含别的质因子的数，题面 n=10 的第 10 个丑数是 12。难点在按顺序不漏不重地生成。

从 1 逐个试除为什么越试越亏

从 1 往上逐个数，反复除 2、3、5，能除尽就是丑数。可丑数越往后越稀疏，第 100 个已是 1536，中间大量整数被白白试除，n 一大就拖垮时间。更快的是让每个新丑数由已有丑数乘 2、3、5 按序造出来。

为什么新丑数都藏在三指针的候选里

除了 1，每个丑数都能写成某个更小的丑数乘 2、乘 3 或乘 5。把已生成的丑数按序存进 dp 数组，dp[i] 就是第 i 个丑数（dp 即动态规划，算过的存下来往后用），dp[1]=1 当起点。下一个丑数就在「已有丑数乘 2、乘 3、乘 5」的候选里。与其全乘出来排序，不如用三个指针 p2、p3、p5 记着 2、3、5 各乘到哪，起初都指向 dp[1]，每步只看 dp[p2]×2、dp[p3]×3、dp[p5]×5。

三指针凭什么不漏也不重地按序生成

每步取最小的候选填进 dp：dp[i]=min(dp[p2]×2,dp[p3]×3,dp[p5]×5)，命中的指针前移。不漏：每个丑数迟早被 ×2、×3、×5 各用一次；不重且按序：每步只取当前最小，填出来天然从小到大。

同一个数可能被两条路造出来：6 既是 3×2 也是 2×3，dp[p2]×2 与 dp[p3]×3 会同时等于 6，只填一个，但 p2、p3 都得前移——只移一个，另一个下一步又会算出 6。所以三个判断是独立的 if，谁等于最小值谁前移，可能同时移两三个。

拿 n=10 把 dp 表一格格填到 12

dp[1]=1，三指针都指向它。第 2 项 min(1×2,1×3,1×5)=2，p2 前移；第 3 项 min(2×2,1×3,1×5)=3，p3 前移；第 4 项 min(2×2,2×3,1×5)=4，p2 前移；第 5 项 min(3×2,2×3,1×5)=5，p5 前移。

第 6 项 min(3×2,2×3,2×5)=6，×2 与 ×3 同时命中，只填一次、p2 与 p3 一起前移。往后取最小：第 7 项 min(4×2,3×3,2×5)=8、第 8 项 =9、第 9 项 min(5×2,4×3,2×5)=10（×2 与 ×5 同时命中）、第 10 项 min(6×2,4×3,3×5)=12。整张表 1、2、3、4、5、6、8、9、10、12 正是前 10 个丑数。

复杂度多少，相等和 dp[1] 两处别写错

生成 n 个丑数，每个只做取最小、移指针的常数操作，O(n) 时间；dp 存下前 n 个丑数，空间 O(n)。

两个坑。一是相等时只移一个指针：多个候选同时等于最小值，得把对应指针全部前移，否则下一步会再造出同一个数，用三个独立 if、别写成 if/elif。二是 dp[1]=1 别漏：1 是第 1 个丑数、三指针的共同起点，漏了整列没法往下乘。

Python

def nthUglyNumber(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    p2 = p3 = p5 = 1
    for i in range(2, n + 1):
        c2, c3, c5 = dp[p2]*2, dp[p3]*3, dp[p5]*5
        dp[i] = min(c2, c3, c5)
        if dp[i] == c2: p2 += 1
        if dp[i] == c3: p3 += 1
        if dp[i] == c5: p5 += 1
    return dp[n]

C++

int nthUglyNumber(int n){
    vector<int> dp(n + 1);
    dp[1] = 1;
    int p2 = 1, p3 = 1, p5 = 1;
    for(int i = 2; i <= n; ++i){
        int c2 = dp[p2]*2, c3 = dp[p3]*3, c5 = dp[p5]*5;
        dp[i] = min({c2, c3, c5});
        if(dp[i] == c2) ++p2;
        if(dp[i] == c3) ++p3;
        if(dp[i] == c5) ++p5;
    }
    return dp[n];
}

Java

int nthUglyNumber(int n){
    int[] dp = new int[n + 1];
    dp[1] = 1;
    int p2 = 1, p3 = 1, p5 = 1;
    for(int i = 2; i <= n; i++){
        int c2 = dp[p2]*2, c3 = dp[p3]*3, c5 = dp[p5]*5;
        dp[i] = Math.min(c2, Math.min(c3, c5));
        if(dp[i] == c2) p2++;
        if(dp[i] == c3) p3++;
        if(dp[i] == c5) p5++;
    }
    return dp[n];
}