面试题49：丑数

从反复除尽2、3、5的逐数判断出发，推导三条有序候选流及三个指针的线性生成算法。

学习目标

能判断一个数是否为丑数（反复除尽 2、3、5 后剩 1）
能解释三条有序候选流与三个指针的线性生成算法
能说明算法 2 的完备性、有序性与不重复证明

从“14为什么不是”开始

先预测：6是2乘3，8是2的三次方，它们都只由允许因子组成；14虽然能被2整除，但除完还剩7，因此不是。

题目表述为“”，准确含义是除1外没有其他，而不是要求2、3、5必须全部出现。2、9、25都合法；7、14、21含其他质因子，不合法。习惯上把1作为第一个。

对任意正整数n，丑数条件可写成：

n = 2^a 3^b 5^c,\qquad a,b,c \in \mathbb{Z}_{\ge 0}.

当a、b、c全为0时n等于1，正好对应题目的基例。

反复除尽2、3、5后若恰好剩1，则原数没有其他质因子；1由题目单独约定为丑数。

作者算法1：逐个自然数判断

最直接的方法从1开始逐个增加number。每个候选都反复除以2，再除以3，再除以5；若最终恰好剩1，它的规范分解中没有其他质因子，计数加1。找到第index个时返回当前number。

bool IsUgly(int number) {
    while (number % 2 == 0) {
        number /= 2;
    }
    while (number % 3 == 0) {
        number /= 3;
    }
    while (number % 5 == 0) {
        number /= 5;
    }
    return number == 1;
}
 
int GetUglyNumber_Solution1(int index) {
    if (index <= 0) {
        return 0;
    }
 
    int number = 0;
    int uglyFound = 0;
    while (uglyFound < index) {
        ++number;
        if (IsUgly(number)) {
            ++uglyFound;
        }
    }
    return number;
}

这个入口先把number从0增加到1，所以不会调用IsUgly(0)。直接调用辅助函数IsUgly(0)却会死循环：0对2取余为0，0除以2仍是0，第一个while永远无法退出。

设目标是第k个丑数，其数值为U_k。算法1检查1到U_k的每个整数；单次反复除法最坏与候选位数同阶，因此可给出上界：

T_1(k) = O\!\left(U_k \log U_k\right), \qquad S_1(k)=O(1).

这个上界不是说每个候选都做满对数次除法，而是揭示运行时间依赖答案数值而非仅依赖序号。第1500个丑数为859963392，逐个扫描到它会浪费绝大多数工作。

从“判断所有数”转为“只生成合法数”

任意大于1的丑数至少含一个2、3或5。除去其中一个因子后，剩下仍是更小的丑数。因此每个非1丑数必能由一个已经生成的丑数乘2、乘3或乘5得到。

反过来，已有丑数乘2、3或5不会引入其他质因子，结果仍是丑数。于是所有待生成值来自三条：

\{2U_j\}_{j\ge 0},\qquad \{3U_j\}_{j\ge 0},\qquad \{5U_j\}_{j\ge 0}.

任务变成三路有序合并并去重，而不是在自然数海洋中逐个判断。

2 × U

2, 4, 6, 8, 10, 12, 16, 18, 20, 24, 30

3 × U

3, 6, 9, 12, 15, 18, 24, 27, 30

5 × U

5, 10, 15, 20, 25, 30

有序合并

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24

每个非1丑数必来自已有丑数乘2、3或5；算法2是在去重合并三条递增流。

这正是原书要求的“按顺序生成而不是逐个判断”。空间换时间的关键不是把IsUgly写得更快，而是彻底不访问不可能成为答案的7、11、13、14等候选。

各自指向什么

保存已生成数组U，并维护p2、p3、p5三个指针。对乘数m，它指向第一个满足m乘U[p_m]严格大于最后已输出值的位置；对应乘积就是该流的。

若当前最后输出U_k，指针定义可写为：

p_m = \min\{j \mid mU_j > U_k\}, \qquad m\in\{2,3,5\}.

下一项取三条流头部的最小值：

U_{k+1} = \min\!\left( 2U_{p_2}, 3U_{p_3}, 5U_{p_5} \right).

输出后，对所有乘积小于或等于新值的指针继续前移，重新建立上述。

拖动序号可看到第6项6同时来自3乘2与2乘3，所以p2、p3都要推进；第9项10来自5乘2与2乘5，所以p2、p5都推进。并列来源称为。

作者算法2：数组与指针

作者用三个裸指针直接指向pUglyNumbers数组元素，而不是保存整数下标。每轮先取三种乘积最小值写入下一格，再分别用while跳过所有不大于新值的乘积。

int Min(int number1, int number2, int number3) {
    int min = number1 < number2
        ? number1
        : number2;
    return min < number3 ? min : number3;
}
 
int GetUglyNumber_Solution2(int index) {
    if (index <= 0) {
        return 0;
    }
 
    int* pUglyNumbers = new int[index];
    pUglyNumbers[0] = 1;
    int nextUglyIndex = 1;
 
    int* pMultiply2 = pUglyNumbers;
    int* pMultiply3 = pUglyNumbers;
    int* pMultiply5 = pUglyNumbers;
 
    while (nextUglyIndex < index) {
        const int min = Min(
            *pMultiply2 * 2,
            *pMultiply3 * 3,
            *pMultiply5 * 5);
        pUglyNumbers[nextUglyIndex] = min;
 
        while (*pMultiply2 * 2 <=
               pUglyNumbers[nextUglyIndex]) {
            ++pMultiply2;
        }
        while (*pMultiply3 * 3 <=
               pUglyNumbers[nextUglyIndex]) {
            ++pMultiply3;
        }
        while (*pMultiply5 * 5 <=
               pUglyNumbers[nextUglyIndex]) {
            ++pMultiply5;
        }
        ++nextUglyIndex;
    }
 
    const int ugly =
        pUglyNumbers[nextUglyIndex - 1];
    delete[] pUglyNumbers;
    return ugly;
}

第一个数组元素必须显式设为1。它不能由“更早丑数乘2、3、5”生成，却是所有三条候选流的共同种子。index等于1时生成循环不进入，直接返回该基例。

三个while看似嵌套在主循环中，但每个指针从数组开头只向右走，整个函数里各自最多推进index次。摊还复杂度是：

T_2(k)=O(k), \qquad S_2(k)=O(k).

为什么必须推进所有

假设生成6时只推进2倍流，3倍流仍停在2乘3等于6。下一轮三路最小值仍会选6，序列出现重复，且若继续只推进单一路，错误可能持续。

源码使用三个独立while，而不是if、else if链。只要某条流当前候选小于或等于刚输出值，就推进到严格更大。这样既消除多个来源的相等值，也防止任何过期候选留在流头。

为什么条件写小于或等于，而不只写等于？在正确不变式下选最小值前没有候选小于最后输出值，等于通常足够；小于或等于更直接表达“跳过所有已输出候选”，也让不变式在维护时更稳健。

完备性、有序性与不重复证明

只生成合法值。 初始1按题意合法；归纳假设数组现有值都是丑数，新值是其中一个乘2、3或5，规范分解只增加允许质因子的指数，因此仍合法。

不会漏掉。 设x是尚未输出的最小丑数。x大于1，可除去一个允许因子m得到更小丑数y。按最小性和归纳假设，y已经输出，因此x等于m乘y，必出现在某条候选流中。三路流头取最小不可能越过x。

保持有序。 每个指针都停在乘积严格大于最后输出值的位置，三者最小值也严格更大。

消除重复。 输出新值后，所有能产生该值的流都越过它；下一轮不可能再次选到同一数。

这四步合起来说明数组恰好按严格递增顺序包含全部丑数。

前15项逐轮核算

序列开头为：

序号:  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
数值:  1  2  3  4  5  6  8  9 10 12 15 16 18 20 24

7被跳过，所以第7项是8；14含因子7，所以11之后不是14而是15。生成12时2倍流给出6乘2，3倍流给出4乘3，两指针同时推进。生成15时3倍流与5倍流并列；生成20时2倍流与5倍流并列。

维度	算法1逐个判断	算法2按序生成
候选来源	自然数1、2、3…	已确认丑数乘2、3、5
判定动作	反复除尽三个因子	取三路最小候选
无效工作	检查大量非丑数	只生成丑数候选
第1500个	扫描到859963392	生成1500项
时间尺度	依赖答案数值	随index线性
辅助空间	常数	保存index个丑数
零边界	入口index为0直接返回	入口index为0直接返回
溢出风险	number持续递增	候选乘法可能溢出

算法2以O(index)内存换掉了对庞大非丑数区间的扫描，是本题的时间优化核心。

算法1保持常数空间，却让耗时取决于U_k；算法2保存前k项，直接让耗时随k线性。题目位于“优化时间和空间效率”章节，意图正是识别这种空间换时间。

分步1 / 3

逐数判断

从 1 开始逐个自然数反复除以 2、3、5，余 1 则是丑数——正确但每个数都要做分解。

反复除尽2、3、5后若恰好剩1，则原数没有其他质因子；1由题目单独约定为丑数。

整数溢出与现代实现

作者的目标第1500项859963392能装入32位有符号int，但通用index继续增大时，数组元素乘2、3、5可能先溢出。带符号溢出在C++中是未定义行为，负候选还可能破坏最小值和指针边界。

现代版本可先用uint64_t计算并在乘法前检查，或使用大整数。只把结果变量改成64位不够，候选乘法的两个操作数也必须在64位类型中。

#include <algorithm>
#include <cstdint>
#include <limits>
#include <stdexcept>
#include <vector>
 
std::uint64_t uglyNumber(std::size_t index) {
    if (index == 0) {
        return 0;
    }
 
    std::vector<std::uint64_t> values(index);
    values[0] = 1;
    std::size_t p2 = 0;
    std::size_t p3 = 0;
    std::size_t p5 = 0;
 
    const auto checkedMultiply =
        [](std::uint64_t value,
           std::uint64_t factor) {
            if (value >
                std::numeric_limits<
                    std::uint64_t>::max() /
                    factor) {
                throw std::overflow_error(
                    "ugly number overflow");
            }
            return value * factor;
        };
 
    for (std::size_t next = 1;
         next < index;
         ++next) {
        const auto c2 =
            checkedMultiply(values[p2], 2);
        const auto c3 =
            checkedMultiply(values[p3], 3);
        const auto c5 =
            checkedMultiply(values[p5], 5);
        values[next] = std::min({c2, c3, c5});
 
        while (checkedMultiply(
                   values[p2], 2) <=
               values[next]) {
            ++p2;
        }
        while (checkedMultiply(
                   values[p3], 3) <=
               values[next]) {
            ++p3;
        }
        while (checkedMultiply(
                   values[p5], 5) <=
               values[next]) {
            ++p5;
        }
    }
    return values.back();
}

这个版本在无法表示下一项时抛错，而不是静默回绕。若接口需要支持任意index，应换用大整数；若只支持到某个上限，应在契约中给出最大index并测试边界。

作者13次测试调用

main依次调用Test：

index 1期望1。
index 2到6依次期望2、3、4、5、6。
index 7到11依次期望8、9、10、12、15，覆盖跳过7、11、13、14。
index 1500期望859963392。
index 0期望0，两个公开入口都立即返回。

合计13次Test，每次都先执行Solution1，再执行Solution2，并只打印passed或failed。

第1500项让算法1从1扫描到859963392，在常规自动化测试中极不经济。忠实度审查要记录作者确实这样调用，但工程测试不应每天重复这个慢基线；可让小index两版对拍，第1500项只运行算法2，并把算法1的大规模测试放入显式性能任务或禁用清单。

#include <cassert>
 
void testUglyNumbers() {
    const int expected[] = {
        1, 2, 3, 4, 5, 6,
        8, 9, 10, 12, 15,
    };
    for (int i = 1; i <= 11; ++i) {
        assert(GetUglyNumber_Solution1(i) ==
               expected[i - 1]);
        assert(GetUglyNumber_Solution2(i) ==
               expected[i - 1]);
    }
 
    assert(GetUglyNumber_Solution2(1500) ==
           859963392);
    assert(GetUglyNumber_Solution1(0) == 0);
    assert(GetUglyNumber_Solution2(0) == 0);
}

还应单独测试安全包装后的IsUgly：负数与0返回false，1返回true，6与8返回true，14返回false。不要直接对原版IsUgly(0)写单元测试，否则测试进程会永久停住。

本章练习

练习

问题 1： 14 为什么不是丑数？判断标准是什么？

问题 2： 算法 2 中三个指针各指向什么？为什么并列时必须同时推进？

问题 3： 算法 2 为什么是线性的？请给出时间与空间复杂度。

本章回顾

丑数除1外只包含因子2、3和5，1按约定是第一项。
算法1逐个增加自然数，并反复除尽三个允许因子判断。
原版IsUgly不接受0；直接传0会陷入无限除2循环。
每个非1丑数都来自更小丑数乘2、3或5，因此可按顺序生成而不是逐个判断。
三个指针分别维护三条候选流的最小未输出乘积。
候选并列时所有相关指针都要推进，保证严格递增和去重。
算法2时间O(index)、空间O(index)，优于依赖答案数值的扫描。
作者执行第1500项的两版测试；工程门禁应保留语义但隔离极慢基线。

名词解释

本章出现的专业名词，用大白话再讲一遍。

丑数: 除 1 外只含 2、3、5 质因子的正整数，如 2、9、25。
候选流: 算法 2 中由"已生成丑数 × 因子"构成的有序候选序列。
并列指针: 产生同一最小候选值的多个指针，必须同时推进以避免重复。
质因子: 一个数的质数因子，丑数的质因子只能是 2、3、5。
候选流: 由"已生成丑数 × 因子"构成的递增候选序列，三流取最小合并。

面试题49：丑数

学习目标

从“14为什么不是”开始

作者算法1：逐个自然数判断

从“判断所有数”转为“只生成合法数”

三个指针↡各自指向什么

作者算法2：数组与指针

为什么必须推进所有并列指针↡

完备性、有序性与不重复证明

前15项逐轮核算

逐数判断

整数溢出与现代实现

作者13次测试调用

本章练习

练习

本章回顾

名词解释

名词解释

讨论

各自指向什么

为什么必须推进所有