【剑指offer】丑数

题目描述

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

思路

首先题意上说只包含质因子2、3和5的数称作丑数，那么就说明一个丑数它一定是由另一个丑数乘以2或者乘以3或者乘以5得到。

所以我们就定义一个vector丑数数组，然后用2或3或5不断乘以这个数组，然后将得到的丑数再添加到数组中，注意添加的过程中要进行排序，即每次都将最小的丑数进行添加。

代码

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index < 7){  //因为1~6都是丑数
            return index;
        }
        vector<int> v;//用来存丑数
        v.push_back(1);
        //一个丑数一定由另一个丑数乘以2或者乘以3或者乘以5得到
        int p2 = 0;//乘以2的丑数的下标
        int p3 = 0;//乘以3的丑数的下标
        int p5 = 0;//乘以5的丑数的下标
        int ans = 0;
        while(v.size() < index){
            //取最小是为了得到的丑数是从小到大排序的
            ans = min(v[p2]*2, min(v[p3]*3, v[p5]*5));
            //将得到的丑数压入vector
            v.push_back(ans);
            //如果得到的丑数是通过乘以2或3或5得到的，就将对应的下标往前移
            if(ans == v[p2]*2) p2++;
            if(ans == v[p3]*3) p3++;
            if(ans == v[p5]*5) p5++;
        }
        return ans;
    }
};