C++關于醜數（判斷醜數+查找第n個醜數）

首先看關于醜數的定義：

醜數： 就是隻包含質因數 2、3 和5 的正整數。

換言之：就是%2，或%3，%5==0；

一、那麼判斷醜數的方法就很簡單：

遞歸法+疊代法

class Solution {
public:
    bool isUgly(int n) {//遞歸法
        if (n == 1)return true;
        if (!n)return false;
        if (n % 2 == 0) return isUgly(n / 2);
        if (n % 5 == 0) return isUgly(n / 5);
        if (n % 3 == 0) return isUgly(n / 3);
        else return false;
    }
    bool  isugly(int m) {//疊代法
        if (m <= 0) return false;
        while (m > 1) {
            if (m % 2 == 0) m = m / 2;
            else if (m % 3 == 0)  m = m / 3;
            else if (m % 5 == 0) m = m / 5;
            else  return false;
        }
        return m == 1;
    }
};
           

二、查找第n個醜數

三指針動态規劃

class Solution {
public:
    int nthUglyNumber(int n) {
     int m=0;
     vector<int> res;
     res.push_back(1);
     int i2=0,i3=0,i5=0;
     for(int i=1;i<n;i++){
         m=min(res[i2]*2,min(res[i3]*3,res[i5]*5));
         res.push_back(m);
         if(m==res[i2]*2)i2++;
         if(m==res[i3]*3)i3++;
         if(m==res[i5]*5)i5++;
     }
     return res[n-1];
    }
    
};
           

利用優先隊列實作

class Solution {
public:
    int nthUglyNumber(int n) {
    priority_queue<double,vector<double>,greater<double>> q;
    q.push(1);
    double ans=1,i=1;
    while(i<=n){
        q.push(ans*2);
        q.push(ans*3);
        q.push(ans*5);
        ans=q.top();
        q.pop();
        while(!q.empty()&&ans==q.top()){
            q.pop();
        }
        i++;
    }
    return ans;
    }
};