超级丑数 图解题解

这道题到底在问什么

n

10

primes

[2, 3, 5]

输出

12

解释

前 10 个：1,2,3,4,5,6,8,9,10,12，第 10 个是 12

先想最直接的笨办法

丑数越往后越稀疏（比如 25 之后下一个可能跳到 27、30），一个个枚举判断会浪费大量功夫在「不是丑数」的数上。我们想只生成丑数本身。（动画第 3 步）

最优解：一步一步想明白

1. 3丑数越往后越稀疏（比如 25 之后下一个可能跳到 27、30），一个个枚举判断会浪费大量功夫在「不是丑数」的数上。我们想只生成丑数本身。
2. 41×2=2、1×3=3、2×2=4……所有丑数都长在「已有丑数」上。于是我们维护一个有序丑数数组，每次从「旧丑数×质数」的候选里挑最小的接到队尾。
3. 5primes=[2,3,5] 就开 3 个指针 p0/p1/p2，各自候选 = primes[j] × ugly[ptr[j]]。三路候选取最小，谁被选中谁的指针就往后挪一格。下面一步步演。
4. 6ugly[0] = 1丑数数组第一格永远是 1（任何质数都不含也算）。三个指针 p0/p1/p2 全指向 ugly[0]=1，于是右边候选是 2、3、5。「·」是还没生成的格子。
5. 7比较 2,3,5右边三路候选 2/3/5，最小的是 2（被高亮那行），它由 p0 贡献。下一帧把它接到队尾。
6. 8ugly[1]=2，p0 前进2 接到队尾成 ugly[1]。是 p0 贡献的，p0 往后挪一格指向 ugly[1]=2，它的新候选变成 2×2=4。p1/p2 没动。
7. 9比较 4,3,5p0 候选已变 4，现在候选 4/3/5，最小是 3（p1 贡献）。
8. 10ugly[2]=3，p1 前进3 接到队尾成 ugly[2]，p1 挪到 ugly[1]，新候选 3×2=6。
9. 11比较 4,6,5候选 4/6/5，最小 4（p0 贡献）。
10. 12ugly[3]=4，p0 前进4 入队成 ugly[3]，p0 挪到 ugly[2]，候选变 2×3=6。注意 p0、p1 的候选现在都等于 6——下面要小心。
11. 13比较 6,6,5候选 6/6/5，最小 5（p2 第一次出手）。
12. 14ugly[4]=5，p2 前进5 入队成 ugly[4]，p2 挪到 ugly[1]，候选 5×2=10。
13. 15现在 p0、p1 候选都是 6。如果只把其中一个指针往后挪，下一步另一个还会再吐一个 6 → 数组里出现两个 6，重复了。正确做法：凡是候选 == 当前最小值的指针，全部一起推进。
14. 16比较 6,6,10候选 6/6/10，最小是 6，但 p0、p1 候选都等于 6！下一帧写一次 6，且两个指针都要推进，否则会重复。
15. 17ugly[5]=6，去重推进最小值 6 只写一次到 ugly[5]，但 p0、p1 两个指针都往后挪：p0→2×4=8，p1→3×3=9。这样下一步就不会再重复吐 6 了——去重的关键就在这。
16. 18比较 8,9,10候选 8/9/10，最小 8（p0 贡献）。注意序列里没有 7——7 不在 primes 里，没有任何候选等于 7。
17. 19ugly[6]=8，p0 前进8 入队成 ugly[6]，p0 挪到 ugly[4]=5，候选 2×5=10。
18. 20比较 10,9,10候选 10/9/10，最小 9（p1 贡献）。两个 10 这次没被选中，它们的指针不动。
19. 21ugly[7]=9，p1 前进9 入队成 ugly[7]，p1 挪到 ugly[3]=4，候选 3×4=12。
20. 22比较 10,12,10候选 10/12/10，最小 10，p0、p2 又一次并列！下一帧写一次 10，两路指针一起推进。
21. 23ugly[8]=10，去重推进只写一次 10 到 ugly[8]，p0、p2 都推进：p0→2×6=12，p2→5×3=15。又一次去重成功。
22. 24min(12,12,15)=12 → 答案 = 12候选 12/12/15，最小 12（p0、p1 并列，都推进）。12 填进最后一格 ugly[9]。数组满了，第 10 个超级丑数就是 12，和示例答案对上！整条序列一个不重、一个不漏地造了出来。
23. 25每个质数都「不漏地」乘遍了前面的丑数三个指针各自从头单向前进、永不回退，整体像三条拉链共同合并出一条有序序列。这正是「多路归并」的思想：每路有序，取队头最小逐个吐出。
24. 26k 是质数个数。每生成一个丑数，扫一遍 k 路候选取最小、推进若干指针，共 n 个 → O(n·k)。只造丑数、不碰非丑数，干净利落。
25. 30第 6 步只推 p0，没推 p1假设第 6 步只推进了 p0（候选 6→8），p1 的候选仍停在 6。下一步取最小又会吐出一个 6 → 序列变成 …,6,6,… 重复了。所以并列最小必须全部推进。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def nthSuperUglyNumber(self, n, primes):
        k = len(primes)
        ugly = [1] * n                 # ugly[0]=1
        idx = [0] * k                  # 每个质数一个指针
        cand = [p for p in primes]     # 候选=primes[j]*ugly[idx[j]]
        for i in range(1, n):
            mn = min(cand)             # 三路取最小
            ugly[i] = mn
            for j in range(k):         # 凡等于最小的指针都推进
                if cand[j] == mn:
                    idx[j] += 1
                    cand[j] = primes[j] * ugly[idx[j]]
        return ugly[n - 1]

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        int k = primes.size();
        vector<long long> ugly(n, 1);          // ugly[0]=1
        vector<int> idx(k, 0);                 // 每质数一指针
        vector<long long> cand(primes.begin(), primes.end());
        for (int i = 1; i < n; i++) {
            long long mn = *min_element(cand.begin(), cand.end());
            ugly[i] = mn;
            for (int j = 0; j < k; j++) {       // 等于最小的全推进
                if (cand[j] == mn) {
                    idx[j]++;
                    cand[j] = (long long)primes[j] * ugly[idx[j]];
                }
            }
        }
        return (int)ugly[n - 1];
    }
};

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int k = primes.length;
        long[] ugly = new long[n];
        ugly[0] = 1;                           // ugly[0]=1
        int[] idx = new int[k];                // 每质数一指针
        long[] cand = new long[k];
        for (int j = 0; j < k; j++) cand[j] = primes[j];
        for (int i = 1; i < n; i++) {
            long mn = cand[0];
            for (int j = 1; j < k; j++) mn = Math.min(mn, cand[j]);
            ugly[i] = mn;
            for (int j = 0; j < k; j++) {       // 等于最小的全推进
                if (cand[j] == mn) {
                    idx[j]++;
                    cand[j] = (long) primes[j] * ugly[idx[j]];
                }
            }
        }
        return (int) ugly[n - 1];
    }
}

复杂度

面试官可能追问