题目是丑数
在这里插入图片描述

  • 丑数是能被2,3,5整除的数,我们可以从1开始构造丑数,某个数a是丑数,那么2a、3a、5a都是丑数
  • 方法一:使用堆实现:使用最小堆,初始堆为空,将最小的丑数1加入堆,每次取出堆中的最小的元素x,并将2x、3x、5x加入堆中。但是可能会出现重复的情况,因此我们多建立一个set集合来去重,只有在set中没有出现的元素才加入到堆中。
    代码如下:
int nthUglyNumber(int n) {
    vector<int>f={2,3,5};
    unordered_set<long long>s;
    priority_queue<long long ,vector<long long>,greater<long long>>pq;
    s.insert(1);
    pq.push(1);
    int ans=0;
    for(int i=0;i<n;i++){
        long long cur=pq.top(); //取出当前的最小的元素
        pq.pop();
        ans=(int)cur; //第n个元素
        for(int j=0;j<3;j++){
            long long next=f[j]*cur;
            if(!s.count(next)){ //如果没出现过 加入堆中
                s.insert(next);
                pq.push(next);
            }
        }
    }
    return ans;
}

方法二:动态规划:

  • 定义dp数组,dp[i]表示第i个丑数,因此dp[1]=1,最终答案为dp[n]。
  • 定义三个指针p2、p3、p5,分别表示下一个丑数是当前指针指向的丑数乘以对应的质因数,初始时,三个指针的值都是1。
  • 当i>=2时,状态转移方程为

    d

    p

    [

    i

    ]

    =

    m

    i

    n

    (

    d

    p

    [

    p

    2

    ]

    2

    ,

    d

    p

    [

    p

    3

    ]

    3

    ,

    d

    p

    [

    p

    5

    ]

    5

    )

    dp[i]=min(dp[p2]*2,dp[p3]*3,dp[p5]*5)

    dp[i]=min(dp[p2]2,dp[p3]3,dp[p5]5)

  • 同时需要比较dp[i]和dp[p2]*2、dp[p3]*3、dp[p5]*5的值是否相等,如果相等对应的指针加一
int nthUglyNumber(int n) {
    vector<int>dp(n+1);
    dp[1]=1;
    int p2=1,p3=1,p5=1; //定义三个指针
    for(int i=2;i<=n;i++){
        int num2=dp[p2]*2;
        int num3=dp[p3]*3;
        int num5=dp[p5]*5;
        dp[i]=min(min(num2,num3),num5);
        if(dp[i]==num2) p2++; //必须是三个if,因为有可能一个值和多个值相等,指针都需要增加
        if(dp[i]==num3) p3++;
        if(dp[i]==num5) p5++;
    }
    return dp[n]; //返回第n个丑数
}