【剑指offer33 丑数】

题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

 

如果用一个个数检测，时间复杂度高，通不过

需要用累乘的方法，用已有的丑数得到后面的丑数，直到第N个

每一个乘的时候，都是去最小的，2 3 5 分别有三个指针位，乘完之后就往后移动，这样再比较就能保证每次获得的丑数是连续挨着的

 

class Solution {
public:
    /*
    bool check(int x){
        while(x%2==0)x/=2;
        while(x%3==0)x/=3;
        while(x%5==0)x/=5;
        if(x==1)return true;
        else return false;
    }*/
    
    
    int GetUglyNumber_Solution(int index) {
        /*
        //会超时 
        if(index==1)return 1;
        int cnt = 0 ;
        int x = 1 ;
        while(1){
            if(check(x)){
                cnt++;
                if(cnt == index)break;
            }
            ++x ;
        }
        return x;*/
        
        if(index<7)return index; //7之前都是丑数
        vector<int> ans(index);
        int t2=0, t3=0 , t5=0;//分别做乘的位置标记
        ans[0]=1 ;
        for(int i=1 ; i<index ; ++i){
            ans[i] = min(ans[t2]*2 , min(ans[t3]*3 , ans[t5]*5));
            if(ans[i] == ans[t2]*2)t2++; //谁做了乘法 就下标往后移动一格
            if(ans[i] == ans[t3]*3)t3++;
            if(ans[i] == ans[t5]*5)t5++;
        }
        return ans[index-1];
    }
};