题目描述
我们把只包含质因子 2、3和5的数称作丑数(Ugly Number)。
例如 6、8都是丑数,但 14不是,因为它包含质因子 7。
求第 n 个丑数的值。
样例
输入:5
输出:5
算法1
多路归并
将所有的丑数组成的集合设为S,将所有的2的倍数的丑数组成的集合设为S2,将所有的3的倍数的丑数组成的集合设为S3,将所有的5的倍数的丑数组成的集合设为S5。那么可以根据S2,S3,S5三路归并求得S。同时在求S2,S3,S5的时候又可以根据S求得。
O(n)
C++ 代码
class Solution {
public:
int getUglyNumber(int n) {
vector<int>v = {1};
n--;
int i = 0,j = 0,k = 0;
while(n--)
{
int t = min(v[i] * 2,min(v[j] * 3,v[k] *5 ));
if(t == v[i] * 2)i++;
if(t == v[j] * 3)j++;
if(t == v[k] * 5)k++;
v.push_back(t);
}
return v.back();
}
};