0264. Ugly Number II ==================== 题目信息 -------- :题号: 0264 :难度: Medium :主题: 数学、序列、质因数 :原题: `LeetCode 0264 `_ :重点: 丑数按从小到大排名、``1`` 是第一个丑数、重复生成的相同数只占一个序列位置 题目重述 -------- 丑数是质因数只包含 ``2``、``3`` 和 ``5`` 的正整数,题目规定 ``1`` 也是丑数。给定整数 ``n``,返回丑数序列按严格递增顺序排列后的第 ``n`` 个元素,其中排名从 1 开始。 ``n`` 位于 ``[1, 1690]``,因此一定存在合法答案,并且答案可以由 32 位有符号整数表示。同一个数即使能由不同乘法路径得到,也只能在有序序列中出现一次,例如 ``6`` 既可写成 ``2 × 3``,也可写成 ``3 × 2``,但只占一个排名。 自建示例 -------- 查询序列中间位置: .. code-block:: text 输入:n = 7 输出:8 解释:前七个丑数依次为 1、2、3、4、5、6、8,所以第 7 个是 8。 查询第一个元素: .. code-block:: text 输入:n = 1 输出:1 解释:题目把 1 定义为丑数,并且它是整个序列的首项。 三个有序生成指针 ---------------- 设已经生成严格递增的丑数数组 ``ugly``,所有下一个候选都可以写成: .. code-block:: text ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5 其中指针分别指向尚未用于生成更大候选的最小位置。下一项取三个候选的最小值; 如果多个候选同时等于该最小值,必须同时推进对应指针,否则同一个丑数会被重复写入序列。 初始 ``ugly[0]=1``,每次新项产生后再根据乘积等于新项的条件推进一个或多个指针。 正确性说明 ---------- 每个大于 1 的丑数都能除以 2、3 或 5 得到更小的丑数,因此它必然会在某个指针候选中出现; 指针只跳过已经生成的候选,三个候选的最小值就是当前未生成丑数中的最小值。同步推进相等候选, 保证序列严格递增且不重复。归纳可知数组中的每一项都是、也恰好是按序排列的丑数。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int nthUglyNumber(int n) { std::vector ugly(n, 1); int i2 = 0, i3 = 0, i5 = 0; for (int i = 1; i < n; ++i) { const long long next = std::min({ 2LL * ugly[i2], 3LL * ugly[i3], 5LL * ugly[i5] }); ugly[i] = static_cast(next); while (2LL * ugly[i2] == next) ++i2; while (3LL * ugly[i3] == next) ++i3; while (5LL * ugly[i5] == next) ++i5; } return ugly[n - 1]; } }; 代码分析 -------- 生成 ``n`` 项,每次只处理三个指针,时间复杂度为 ``O(n)``,数组空间为 ``O(n)``。 乘积在 ``long long`` 中计算,避免候选相乘时先发生窄整数溢出;三个 ``while`` 是去重的关键, 例如生成 6 时 2 指针和 3 指针都必须推进。