[sword finger offer] interview question 49: ugly number

Method 1 ： Order to judge

By traversing from 1 Each number at the beginning gets the result , Algorithm efficiency is not very high

class Solution {
    
public:
    int nthUglyNumber(int n) {
    
        if( n <= 0 )
            return 0;
        int index_number = 0;
        int Ugly_number = 0;
        while ( Ugly_number < n)
        {
    
            ++index_number;
            if( IsUgly(index_number) )
                Ugly_number++;
        }
        return index_number;
    }
    
    bool IsUgly(int number)
    {
    
        while( number % 2 == 0 )
            number /= 2;
        while( number % 3 == 0 )
            number /= 3;
        while( number % 5 == 0 )
            number /= 5;
        return ( number == 1 ) ? true : false;
    }
};

Method 2 ： Space for time

The efficiency of the previous algorithm is slow because we need to calculate it whether it is ugly or not .
So you can try to find a way to calculate only ugly numbers , Don't spend time on integers that are not ugly numbers .

class Solution {
    
public:
    int nthUglyNumber(int n) {
    
        vector<int> dp(n,0);
        dp[0] = 1;
        int p2 = 0,p3 = 0,p5 = 0;
        for( int i = 1; i < n; i++ )
        {
    
            dp[i] = min( min( dp[p2]*2, dp[p3]*3), dp[p5]*5 );
            if(dp[i] == dp[p2] * 2)
                p2++;
            if(dp[i] == dp[p3] * 3)
                p3++;
            if(dp[i] == dp[p5] * 5)
                p5++;
        }
        return dp[n-1];
    }
};