题目陈述
描述:把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
算法一:质因数分解(暴力)
算法实现
- 一个很朴素的做法
- 从
每次+1,一直枚举,直到找到地N个丑数为止
- 那么还有一个待解决的问题,如何判断当前数字是不是丑数呢?
- 我们总结一下丑数的性质:只能分解为2,3,5的如干次幂相乘的数,即设第
个丑数为
,则
- 那么我们只需要通过质因数分解,判断他分解2,3,5后,是否为1,如果为1,则说明没有其他的因数,否则则有其他因数,那么他就不是一个丑数
代码实现
class Solution { public: bool check(int x){//判断x是否是仅由2,3,5三个因子组成的数字 while(x%2==0)x/=2; while(x%3==0)x/=3; while(x%5==0)x/=5; return x==1;//如果x此时不为1,则说明x还含有其他的质因数 } int GetUglyNumber_Solution(int idx) { int now=1; vector<int> v(1,1);//放入1个1 while(1){ if(v.size()==idx){//找到地idx个丑数 return v[v.size()-1]; } now++; if(check(now)){//now为丑数 v.push_back(now);//now入队 } } } };
复杂度分析
- 时间复杂度
,其中
为第n个丑数的大小,因为丑数的可能会达到INT_MAX那么大,所以这个算法最坏,可能是一个1e9(甚至更高)级别的算法
- 只能通过11/13的数据,所以我们仍需要寻找更优的算法
算法二:集合+优先队列
思路引入
- 我们试一下能否找到相邻丑数之间的规律,或者丑数生成的规律?
- 比较遗憾的是,我们通过模拟发现,相邻的丑数之间并没有规律,那么这题的另一个切入点,就是生成丑数
思路推进
- 我们可以发现,对于
,它必然是由
乘以2或3或5生成的
- 如果对于
也有
,那么必然也有
乘以2或3或5生成
- 所以,如果知道前面n-1个丑数,我们可以每个数都乘以2,3,5,然后检查出里面跟前面n-1个丑数不重复的并且是最小的数,得到的便是第n个丑数
考虑复杂度
- 不借助set,每次检查重复的复杂度为
,每个丑数生成三个新的,最多有
个丑数,时间复杂度
- 如果借助set去重,每次检查重复的复杂度为
,时间复杂度
- 取出最小值,如果借助堆的话,对于维护堆,每次插入一个数,花费
,最多插入3n次,每次取出最小值,花费
- 当然这个算法是可以AC的,我瞅了一眼,题解区貌似只有我一个人题解写了这个算法
- 事实上,如果直接看其他题解的正解,三指针做***觉得自己一下子似懂非懂
- 实际比赛的时候,除非是巨强的神犇,几乎人没有能一下子就想到最后的三指针算法,不然往往都会有一个思路递进的过程
代码实现
- 注意,此处,进入小顶堆的元素可能会有重复,比如(23和32),所以我们需要去重,这一点我们可以用STL容器中的set,内嵌红黑树,begin即是最小的元素,插入和删除的代价都是
typedef long long ll; class Solution { public: int GetUglyNumber_Solution(int idx) { if(idx<1)return 0; set<ll> s,s_q;//用set来表示队列,同时起到去重的作用 s.insert(1); vector<ll> v(1,1);//放入1个1 int p=0; int e[3]= {2,3,5}; while(v.size()<idx) { for(int i=0; i<3; i++) { if(s.find(e[i]*v[p])==s.end()) {//该新元素,未在前面出现过 s_q.insert(e[i]*v[p]);//此处还需要考虑堆中有重复元素 } } p++; v.push_back(*s_q.begin());//插入新丑数 s.insert(*s_q.begin());//插入新丑数 s_q.erase(s_q.begin());//弹出堆中最小值 } return v[idx-1]; } };
- 接下来,我们思路进一步递进,即我们的正解,三指针做法
算法三:三指针做法
算法思路
- 我们会发现判断是否跟前面重复这个过程,以及维护小顶堆,会花费大量时间,不妨想一想能不能省略去这个过程?
- 我们可以发现,如果已经知道[1~i]个丑数,假如i足够小(
),那么是不是
每个数都会乘以2,3,5再次放入这个队列中
- 如果当前数是由
得到的,那么下一个因为乘以2而得到的丑数,**必然是由
得到的**(后面的数乘以2,必然大于这个数),对于3,5同理
- 所以我们可以利用这个单调性,维护三个指针,依次比较三个指针所指向的数所生成的新丑数,即可
得出第n个丑数
- 即维护i,j,k指针,其中i,j,k分别为指向下一个2,3,5可能成为下一个丑数的数的位置的指针,我们就可以在*三个指针所对应的数的乘以相应的数的运算结果中,找到下一个丑数**
动画演示
代码实现
- 注意,下面的if,不能写成if-else,因为可能出现v[i]2==v[j]3这样的情况,这种情况我们就需要同时移动i,j
- 否则,数组v中就可能出现重复的元素,导致错误答案
C++
class Solution { public: int GetUglyNumber_Solution(int idx) { int i=0,j=0,k=0,now;//i,j,k分别为指向下一个*2,*3,*5可能成为下一个丑数的数的位置的指针 vector<int> v(1,1);//放入1个1 while(v.size()<idx){//v中的数量为为idx时候,停止循环 now=min(v[i]*2,min(v[j]*3,v[k]*5));//三个指针运算的结果中找,下一个丑数 v.push_back(now);//将下一个丑数入队 if(v[i]*2==now)i++;//下一个丑数可以由v[i]*2得到,则i指针后移 if(v[j]*3==now)j++;//下一个丑数可以由v[j]*3得到,则j指针后移 if(v[k]*5==now)k++;//下一个丑数可以由v[k]*5得到,则k指针后移 //此处不能写if -else ,因为可能存在v[i]*2==v[j]*3这种情况 //那么在下一次循环中,v[j]*3就会被再次选中,这样就会造成v中有重复元素出现 } return v[idx-1];//此处元素不能写now,当idx==1时被hack } };
Python
class Solution: def GetUglyNumber_Solution(self, idx): if idx<1:#非法输入的情况 return 0 lst=[1] i=0#i为指向下一个*2可能成为下一个丑数的数的位置的指针 j=0#j为指向下一个*3可能成为下一个丑数的数的位置的指针 k=0#k为指向下一个*5可能成为下一个丑数的数的位置的指针 while len(lst)<idx :#当得到第idx个丑数的时候,循环停止 now=min(lst[i]*2,lst[j]*3,lst[k]*5)#三个指针运算的结果中找,下一个丑数 lst.append(now)#将下一个丑数入队 if now==lst[i]*2:#下一个丑数可以由v[i]*2得到,则i指针后移 i+=1 if now==lst[j]*3:#下一个丑数可以由v[j]*3得到,则j指针后移 j+=1 if now==lst[k]*5:#下一个丑数可以由v[k]*5得到,则k指针后移 k+=1 return lst[idx-1]#返回答案,如果idx==1,now没有定义,依旧会CE,所以此处不能写now