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 指针都必须推进。