丑数（广搜）

题意

找第n个丑数,丑数:只包含2,3,5质因子的数

思路分析

考虑合法值

因为只是2,3,5的倍数,所以合法的值表示为 $2^{p_2}3^{p_3}5^{p_5}$

从小到大维护

从第一个找到第n个,每一次需要找还未找到过的最小值

通过set或小根堆,都可以实时的维护还未扩展的最小值,(小根堆要注意的是需要手动处理重复值

候选最小值

当一个值被选择时,如果它是 $2^{p_2}3^{p_3}5^{p_5}$

那么 $2^{p_2+1}3^{p_3}5^{p_5}$ , $2^{p_2}3^{p_3+1}5^{p_5}$ , $2^{p_2}3^{p_3}5^{p_5+1}$ 都还未被选择

且如果有各个幂次都大于当前幂次的值 $2^{q_2}3^{q_3}5^{q_5},q_2 > p_2,q_3 > p_3,q_5 > p_5$ ,它比这三个值都大,一定在这三个值之后

因此每个被选值,可以扩展出三个候选值

题目样例

以题目样例n=7为例, 候选值如图所示,最后输出候选值中最小的即可

alt

题解

所以整合上面的内容

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index == 0) return 0;
        set<long long> s; // 候选值
        s.insert(1); // 初始值
        while(s.size()){
            auto v = *s.begin(); // 最小的
            s.erase(s.begin());
            if(!--index)return v; // 满足个数
            s.insert(v*2); // 扩展*2
            s.insert(v*3); // 扩展*3
            s.insert(v*5); // 扩展*5
        }
        return -1;
    }
};

复杂度分析

空间复杂度: 用了set保存扩展还未选择的数,大小和查找的个数相当,所以空间复杂度为 $O (n)$

时间复杂度: 每次取最小的,每次扩展3个,都是常数级别,所以时间复杂度为 $O (n)$

题解 | #丑数#