49. ugly number

The finger of the sword Offer 49. Ugly number

Ideas ： Dynamic programming

Let the known length be n Sequence of ugly numbers $x_1,x_2,x_3,\cdots ,x_n$, Please n+1 Ugly number , According to the recursive nature , Ugly number $x_{n+1}$ It can only be for ：
$$f(x)=\{\begin{array}{ll}{x}_a\times 2& a\in [1,n]\\ x_b\times 3& b\in [1,n]\\ x_c\times 5& c\in [1,n]\end{array}$$
The recurrence formula of ugly numbers is ：

$x_{n+1}=min(x_a\times 2,x_b\times 3,x_c\times 5)$

because $x_{n+1}$ Is the closest to $x_n$ Ugly number , So index a, b, c The following conditions are met ：
$$\{\begin{array}{ll}{x}_a\times 2>x_n\ge x_{a-1}\times 2& namely{x}_{a}byThe\; firstindividualrideWith2afterBigOn{x}_{n}OfuglyCount\\ x_b\times 3>x_n\ge x_{b-1}\times 3& namely{x}_{b}byThe\; firstindividualrideWith3afterBigOn{x}_{n}OfuglyCount\\ x_c\times 5>x_n\ge x_{c-1}\times 5& namely{x}_{c}byThe\; firstindividualrideWith5afterBigOn{x}_{n}OfuglyCount\end{array}$$
therefore , Set the pointer a,b,c Point to the first ugly number , The next ugly number is obtained by the circular recurrence formula , And each round will correspond to the pointer +1

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n);
        dp[0]=1;
        int a=0,b=0,c=0;
        for(int i=1;i<n;++i){
            int na=dp[a]*2;
            int nb=dp[b]*3;
            int nc=dp[c]*5;
            dp[i]=min(na,min(nb,nc));
            if(dp[i]==na)++a;
            if(dp[i]==nb)++b;
            if(dp[i]==nc)++c;
        }
        return dp[n-1];
    }
};

Time complexity O(n)

Spatial complexity O(n)

Ideas : Heap + Hash table de duplication

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> factors={2,3,5};
        unordered_set<long> seen;
        priority_queue<long,vector<long>,greater<long>> heap;
        seen.insert(1L);
        heap.push(1L);
        int ugly=0;
        for(int i=0;i<n;++i){
            long curr=heap.top();
            heap.pop();
            ugly=int(curr);
            for(int factor:factors){
                long next=curr*factor;
                if(!seen.count(next)){
                    seen.insert(next);
                    heap.push(next);
                }
            }
        }
        return ugly;
    }
};

Time complexity O(n*logn)

Spatial complexity O(n)