欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode练习 #264 Ugly Number II

程序员文章站 2022-04-24 15:42:30
...

Leetcode练习 #264 Ugly Number II




题目简析:题目要求找出第N个丑陋数,根据丑陋数的特点,丑陋数只有因数2 3 5,因此当N到达一定数字时,丑陋数的大小会非常大,因此这道题目需要思考一个时间复杂度比较低的算法。

       我的第一个算法是,维护一个包含特殊数字的数组A,从num=1开始,假如这个num满足以下条件,那么就放到数组A里,反之则放到丑陋数B中:

(1)  num既不能被2,也不能被3、5整除

(2)  假如能被2、3、5三者其中之一整除,整除后的商的数字在数组A中

同时,为了使得在数组A中的检索时间复制度达到极限O(1),我令A中所有数都是0,但是检测到满足(1)(2)的数组时,采用A[num]=-1的方式储存数组,即牺牲非常大的空间来换取时间。但是,最后提交时,估计空间过大,因此不能通过。

换言之,在已有的数组中进行检索,要么空间复杂度过高,要么时间复杂度过高(即使是二分查找O(log) ),所以要抛弃检索这个环节。因此第二个算法就是,让数组ugly={1},每次选择一个符合条件的最小丑陋数依次加入。

根据丑陋数的特点,我们可以归纳为,一个新的丑陋数是从已有的丑陋数中之一与2,3,5相乘所得,因此我们每一轮从三者选择一个最小值就行。

       我们尝试写出三组丑陋数,分别是丑陋数序列(斜体数字) x 2 / 3 /5,如下

1*2    2*2    3*2    4*2    5*2……….

1*3    2*3    3*3    4*3    5*3……….

1*5    2*5    3*5    4*5    5*5……….

 

其中丑陋数序列为 1 2  3  4 5  6  8 9  10 ……….

 

所以我们维护三个数组(或者队列),每个数组分别有一个下标,每个下标表示这个数组的第几个丑陋数,我们假设三个数组分别为 g2,g3. g5  下标分别为p2  p3  p5,以下我们模仿以下添加前几个丑陋数,p2 p3 p5初始均为0

第一轮:g2=0, g3=0, g5=0 àg2[p2]=2,g3[p3]=3, g5[P5]=5, 选取g2[p2]=2加入丑陋数,g2++

 

第二轮:g2=1, g3=0, g5=0 àg2[p2]=4,g3[p3]=3, g5[P5]=5, 选取g3[p3]=3加入丑陋数,g3++

 

第三轮:g2=1, g3=1, g5=0 àg2[p2]=4 g3[p3]=6,g5[P5]=5, 选取g2[p2]=4加入丑陋数,g2++

 

第四轮:g2=2, g3=1, g5=0 àg2[p2]=6, g3[p3]=6,g5[P5]=5, 选取g5[p5]=5加入丑陋数,g5++

 

第五轮:g2=2 g3=2, g5=21àg2[p2]=6, g3[p3]=6,g5[P5]=10, 选取g2[p2]=6加入丑陋数,g2++

 

 

补充的是,每组的丑陋数可以通过2*ugly[g2] 或者3*ugly[g3]  5*ugly[g5]获取每组的下一个丑陋数,以及避免重复的丑陋数(比如2*3=6 和3*2=6),每一次添加丑陋数都要与上一个丑陋数对比,避免重复。

 

下面附上代码

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int>group2={2};
        vector<int>group3={3};
        vector<int>group5={5};

        int p2=0;
        int p3=0;
        int p5=0;
        vector<int> ugly={1};

        
        while(ugly.size()<=n){
            int min_num=min_ele(group2[p2],min(group3[p3],group5[p5]));
            
            if(ugly[ugly.size()-1]!=min_num)
                ugly.push_back(min_num);

            if(group2[p2]==min_num){

                group2.push_back(2*ugly[++p2]);
          
            }
            else if(group3[p3]==min_num){

                group3.push_back(3*ugly[++p3]);
                          
            }
            else if(group5[p5]==min_num){
                
                group5.push_back(5*ugly[++p5]);
                         
            }
                
        }

        return ugly[n-1];
        
    }
    int min_ele(int num1, int num2){
        if(num1>num2)
            return num2;

        return num1;
    }
    
    
};