题目陈述

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

算法一：质因数分解（暴力）

算法实现

一个很朴素的做法
从 $1 \sim \infty$ 每次+1，一直枚举，直到找到地N个丑数为止
那么还有一个待解决的问题，如何判断当前数字是不是丑数呢？
我们总结一下丑数的性质：只能分解为2,3,5的如干次幂相乘的数，即设第 $i$ 个丑数为 $u_n$ ，则 $u_n=2^x \times 3^y \times 5^z$

那么我们只需要通过质因数分解，判断他分解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入队
          }
      }
  }
};

复杂度分析

时间复杂度 $O(u_n)$ ，其中 $u_n$ 为第n个丑数的大小，因为丑数的可能会达到INT_MAX那么大，所以这个算法最坏，可能是一个1e9（甚至更高）级别的算法
只能通过11/13的数据，所以我们仍需要寻找更优的算法
算法二：集合+优先队列

思路引入
我们试一下能否找到相邻丑数之间的规律，或者丑数生成的规律？
比较遗憾的是，我们通过模拟发现，相邻的丑数之间并没有规律，那么这题的另一个切入点，就是生成丑数
思路推进
我们可以发现，对于 $u_n,(n>1)$ ,它必然是由 $u_i(i\in [1,n-1])$ 乘以2或3或5生成的
如果对于 $i$ 也有 $i>1$ ，那么必然也有 $u_j,(j \in [1,i-1])$ 乘以2或3或5生成 $u_i$
所以，如果知道前面n-1个丑数，我们可以每个数都乘以2,3,5，然后检查出里面跟前面n-1个丑数不重复的并且是最小的数,得到的便是第n个丑数
考虑复杂度
不借助set，每次检查重复的复杂度为 $O(n)$ ，每个丑数生成三个新的，最多有 $(n-1)$ 个丑数，时间复杂度 $O(3n^2)$
如果借助set去重,每次检查重复的复杂度为 $O(\log n)$ ,时间复杂度 $O(3n \log n)$
取出最小值，如果借助堆的话，对于维护堆，每次插入一个数，花费 $O(log(3n))$ ,最多插入3n次，每次取出最小值，花费 $O(1)$
当然这个算法是可以AC的，我瞅了一眼,题解区貌似只有我一个人题解写了这个算法
事实上，如果直接看其他题解的正解，三指针做***觉得自己一下子似懂非懂
实际比赛的时候，除非是巨强的神犇，几乎人没有能一下子就想到最后的三指针算法，不然往往都会有一个思路递进的过程
代码实现

注意，此处，进入小顶堆的元素可能会有重复，比如(23和32)，所以我们需要去重，这一点我们可以用STL容器中的set，内嵌红黑树，begin即是最小的元素,插入和删除的代价都是 $O(\log 2n)$

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足够小（ $i*5<u_n$ ），那么是不是 $u_1 \sim u_i$ 每个数都会乘以2,3,5再次放入这个队列中
如果当前数是由 $u_n=u_j*2$ 得到的，那么下一个因为乘以2而得到的丑数，**必然是由 $u_{j+1}*2$ 得到的**（后面的数乘以2，必然大于这个数）,对于3,5同理
所以我们可以利用这个单调性，维护三个指针，依次比较三个指针所指向的数所生成的新丑数，即可 $O(n)$ 得出第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

题解 | #丑数#

题目陈述

算法一：质因数分解（暴力）

算法实现

代码实现

复杂度分析

算法二：集合+优先队列

思路引入

思路推进

考虑复杂度

代码实现

算法三：三指针做法

算法思路

动画演示

代码实现

C++

Python