大连网站建设-中国互联搜索竞价

给你一个整数 n ，请你找出并返回第 n 个 丑数 。丑数 就是质因子只包含 2、3 和 5 的正整数。

//用一个数组来保存第1到第n个丑数
//一个丑数必须是乘以较小的丑数的 2、3 或 5来得到。
//使用三路合并方法：L2、L3 和 L5三个指针遍历2、3、5倍的丑数序列。
//假设你有第 k 个丑数，那么 第k+1 个必须是 Min（L1 * 2， L2 * 3， L3 * 5）。
//1 通常被视为丑数
class Solution {
public:int nthUglyNumber(int n) {vector<int> ans;ans.push_back(1);int i = 0, j = 0, k = 0;for (int a = 1; a < n; a++) {int u1 = 2 * ans[i];int u2 = 3 * ans[j];int u3 = 5 * ans[k];ans.push_back(min(u1, min(u2, u3)));if (ans[a] == u1)i++;if (ans[a] == u2)j++;if (ans[a] == u3)k++;}return ans[n - 1];}
};

时间复杂度：O(n)
空间复杂度：O(n)