LeetCode 264. 丑数 II

◎

本节目标

以三个有序候选指针生成去重的丑数序列。

查看原题

返回数学建模框架

题意与约束

丑数的质因数只包含 2、3、5；1 也是丑数。返回第 n 个，题目范围到 1690。

第一反应与瓶颈

逐个整数分解质因数能判定丑数，却会浪费在大量非丑数上。它不是纯数论题：关键是把已生成序列按三个倍率归并，具有动态规划与多指针特征。

数学关系与算法推导

每个后续丑数都来自已有丑数乘 2、3 或 5。维护三个指针，它们各自指向尚未使用的最小候选；下一个数取三者最小值。若多个候选同时相等，所有对应指针都要前进。

正确性依据

三个候选序列均递增，取最小值不会跳过任何可能的下一个丑数。每个乘法闭包中的数都有一个较小的丑数前驱，因而会被某个候选产生。同步移动全部命中指针排除了不同乘法路径造成的重复。

样例执行过程

序列从 1 开始：候选为 2, 3, 5，依次得到 2, 3, 4, 5, 6。生成 6 时 2×3 与 3×2 同时命中，所以两个指针一起移动。

代码实现

C++

C++17

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<long long> ugly(n, 1);
        int index2 = 0;
        int index3 = 0;
        int index5 = 0;
        for (int i = 1; i < n; i++) {
            const long long next = min({ugly[index2] * 2, ugly[index3] * 3, ugly[index5] * 5});
            ugly[i] = next;
            while (ugly[index2] * 2 == next) {
                index2++;
            }
            while (ugly[index3] * 3 == next) {
                index3++;
            }
            while (ugly[index5] * 5 == next) {
                index5++;
            }
        }
        return static_cast<int>(ugly[n - 1]);
    }
};

Python

Python 3

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        ugly = [1] * n
        index2 = index3 = index5 = 0
        for i in range(1, n):
            nxt = min(ugly[index2] * 2, ugly[index3] * 3, ugly[index5] * 5)
            ugly[i] = nxt
            while ugly[index2] * 2 == nxt:
                index2 += 1
            while ugly[index3] * 3 == nxt:
                index3 += 1
            while ugly[index5] * 5 == nxt:
                index5 += 1
        return ugly[-1]

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(n)。

边界与易错点

• n = 1 直接对应 1。
• 候选乘积使用更宽整数，避免中间值溢出。
• 不能用 else if 只移动一个命中指针，否则会重复写入候选值。

模式迁移

这是多个递增生成序列的去重归并模型；可迁移到有序状态生成、受限因子序列和若干指针共同推进的动态规划问题。