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