leetcode 264 丑数II

快来打我* 2022-02-28 12:38 234阅读 0赞

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

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();
    	}
    }