GroupBlog

我的算法水平算是很差的那种。。这道题一开始自己想得办法一直都是超时，看了大牛们的思路之后，恍然大悟在此做一个总结

1.题目名称
Ugly Number II (丑数2：返回第n个丑数)
丑数即为由2，3，5作为质因子来组成的数
eg :1,2,3,4,5,6,8
2.说明
丑数具有如下的特征，1是一个特殊的丑数，丑数可以表示为有限个2，3，5的乘积

思路：丑数是由2，3，5的有限个乘积来进行组成，那么我们可以通过之前的丑数来生成后面的丑数，于是我们可以联想到维护一个数组，在数组里存储丑数，这里有一个问题，怎么产生有序的数组？
我们可以假设我们已经有了一个有序的丑数数组，将数组中的每个元素乘2，将大于数组中最大的元素即为M2，将数组中的每一个元素乘3，将大于数组中最大的元素即为M3,将数组中的每一个元素乘5，将大于数组中的最大的元素即为M5,数组中的下一个元素必定会是min(M2,M3,M5)
事实上，我们并不需要这么做，会有一些重复计算包含在里面，可以分别维护三个指针，，三个指针分别表示当前序列中乘2便超出序列的最大数字，乘3便超出序列的最大数字和乘5便超出序列的最大数字。下一个数字一定是这三个数字分别乘以2、3、５中的最小值。

首先展示一个tel的方法

 class Solution 
 {
   public:
   int nthUglyNumber(int n) {    
        if (n <= 1)
         {
            return 1;
        }
        int counter = 0;
        for (int i = 1; ; i++)
         {            
                 if (isUgly(i)) 
                 {
                counter++;
                if (counter == n)
                 {
                    return i;
                }
            } 
        }
        public:
           bool isUgly(int num)
           {
           			if(num <= 0)
           			{
           					return false;
           			}
           			while(n%2 == 0)
           			{
           			num / = 2;
           			}
           			   while(n%3 == 0)
           			   {
           			   			num /= 3;
           			   			}
           			   			while(n%5 == 0)
           			   			{
           			   				num/=5;
           			   				}
           			   				if(num == 1)
           			   				{
           			   							return true;
           			   							}
           			   							else
           			   							{
           			   							return false;
           			   							}
           }
    }

第二种方法:

class Solution
{
	public:
	
int UglyNumber(int n)
	{
	vector<int> number{1};
        int test2 = 0, test3 = 0, test5 = 0;
        while(n > 0)
        {
            int val = min(number[test2]*2, min(number[test3]*3, number[test5]*5));
            vec.push_back(val);
            while(number[test2]*2 <= val)
            	 test2++;
            while(number[test3]*3 <= val) 
            	test3++;
            while(number[test5]*5 <= val) 
            	test5++;
            n--;
        }
        return vec.back();
	}
}