33.丑数.md

33.丑数

题目描述

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

 

解题思路

下面的思路来自《剑指offer》。

首先找丑数的规律，质数就是除了1和它本身以外没有其他的因子，丑数就是除了2,3,5以外没有其他的质因子，也就是说，如果一个数是丑数，那么它一定是由2,3,5相乘得到的，即一定可以写成这样的形式：$p = 2^{x} * 3^{y} * 5^{z}$。

• 思路一，笨办法。如果把一个数不停地除以5，直到除不尽，然后再分别不停地除以3和2，也是直到除不尽，如果最后的结果是1的话，就说明这个数是丑数。那么可以从1开始对每个数都判断，直到总共找到N个丑数为止。但是这样效率实在是太低了，好处是不需要占用太多空间。
• 思路二，空间换时间。既然已经知道丑数的公式$p = 2^{x} * 3^{y} * 5^{z}$，就可以让x,y,z分别从0开始，然后不停地增大，依次算出所有的丑数就行，并且可以把已经求出来的丑数存在数组中。但是需要保证从小到大的顺序，比如已经求出的丑数为[1,2,3,4,5,6,8]，那么下一个数该怎么求呢？下一个数肯定是数组中某个数乘以2或者某个数乘以3或者某个数乘以5的结果，如果方法笨一点的话可以把数组中每个数都分别乘以2,3,5，找到刚好大于数组最大值的那个数。但是这样肯定是效率太低了。由于数组中每个数乘以2或3或5得到的都是丑数，因此数组中一定存在这样的三个位置指针p2,p3,p5，使得p2之前的数乘以2总是小于当前最大的丑数，p2后面的数乘以2总是大于当前最大的丑数，p3和p5也是类似的。我们只需要记录这三个位置，每次得到下一个丑数以后将相应的位置指针+1即可。

 

代码

• 思路二

class Solution {
public:
    int GetUglyNumber_Solution(int n) {
        if(n<7) return n;
        vector<int> result(n);
        result[0]=1;
        int p2=0, p3=0, p5=0;
        for(int i=1; i<n; i++){
            int n2 = result[p2]*2;
            int n3 = result[p3]*3;
            int n5 = result[p5]*5;
            result[i] = min(n2, min(n3, n5));
            // 由于这三个数有可能相同，因此要分别判断，不能用else if
            if(result[i]==n2) p2++;
            if(result[i]==n3) p3++;
            if(result[i]==n5) p5++;
        }
        return result[n-1];
    }
};