33、丑数

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

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index<=0)
            return 0;
        vector<int> rec(index,1);
        int p2=0,p3=0,p5=0,i=1;
        
        while(i<index)
        {
            rec[i] = min(rec[p2]*2,min(rec[p3]*3,rec[p5]*5)); //将丑书依次排序
            while(rec[p2]*2<=rec[i])   //将丑数排序,找到离rec[i]最近的前一个,然后再把p2+1,最后判断和比较的时候就可以得到相对较小的那一个
                p2++;
            while(rec[p3]*3<=rec[i])
                p3++;
            while(rec[p5]*5<=rec[i])
                p5++;
            i++;
        }
        return rec[index-1];
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容