剑指 Offer 49. 丑数

剑指 Offer 49. 丑数

难度：$middle$

题目描述

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

1. $1$ 是丑数。
2. $n$ 不超过 1690。

注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/

算法

(三指针)

依次枚举所有的丑数，然后求出其中的第 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();}
};