62. 丑数
题目描述
我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。
例如 6、8 都是丑数,但 14 不是,因为它包含质因子 7。
求第 n 个丑数的值。
数据范围
1≤n≤1000
样例
输入:5
输出:5
算法1 多路归并
算法流程
假设丑数序列为s,2的倍数为s2,3的倍数为s3, 5的倍数为s5
易得 $s = {1} \bigcup s2 \bigcup s3 \bigcup s5$
所以可以用三路归并,每次选最小值的方式来得到序列s
每次进行归并时,没有必要把3个序列全部算出来
因为 $s2 / 2 == s, s3 / 3 == s, s5 / 5 == s$
即可以由丑数序列计算出3个序列
且丑数序列指针一定先到n(每次必移动一位),其他三个序列指针一定不会越界(要么1位要么不动)
时间复杂度
$O(n)$
C++ 代码
class Solution {
public:
int getUglyNumber(int n) {
vector<int> q(1, 1); //初始时候第一项为1
int i = 0, j = 0, k = 0; //分别指向3个序列的起始
while(--n) //第一个默认是1
{
int t = min(q[i] * 2, min(q[j] * 3, q[k] * 5));
q.push_back(t);
if(t == q[i] * 2) i++;
if(t == q[j] * 3) j++;
if(t == q[k] * 5) k++;
}
return q.back();
}
};
总结
算法的尽头是数学,y总太强了