剑指 Offer 49. 丑数
剑指 Offer 49. 丑数
难度： m i d d l e \color{orange}{middle} middle
题目描述
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
- 1 1 1 是丑数。
- n n n 不超过 1690。
注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/
算法
(三指针)
依次枚举所有的丑数，然后求出其中的第 n 个丑数。
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)
-
空间复杂度 : O ( n ) O(n) O(n)
C++ 代码
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> q(1, 1);
int i = 0, j = 0, k = 0;
while (--n)
{
int t = min(q[i] * 2, min(q[j] * 3, q[k] * 5));
q.push_back(t);
if(q[i] * 2 == t ) i++;
if(q[j] * 3 == t ) j++;
if(q[k] * 5 == t ) k++;
}
return q.back();
}
};