剑指Offer——丑数

题目描述

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

输入
7
返回值
8

题解

• 暴力：初始一个丑数队列，第一个丑数为1。第二个丑数为队列中丑数（1）与2、3、5乘积的最小值（1x2），第三个丑数为队列中丑数(1,2)与2、3、5乘积的最小值（1x3），第四个丑数为队列中丑数（1,2,3）与2、3、5乘积的最小值（2x2）。以此类推，即下一个丑数为：队列中丑数与2、3、5乘积的最小值（去重）。

  • 设置3个队列，分别存放队列中丑数与2、3、5的乘积。
  • 每次从3个队列取出最小值加入丑数队列，并将其与2、3、5的乘积分别加入3个队列中。直到找到目标丑数。

    丑数队列：1 2 3 4 5 6 7
    乘2队列： 2 4 6 8 10 12 14
    乘3队列： 3 6 9 12 15 18 21
    乘5队列： 5 10 15 20 25 30 35

• 优化

  • 3个队列中的数正好是丑数队列中数与2、3、5的乘积，因此可以使用指针表示队列当前队首元素的位置。当取出队首元素加入丑数队列时，指针后移即可。

    import java.util.ArrayList;
    public class Solution {
    public int GetUglyNumber_Solution(int index) {
    // 边界
      if(index<1){
          return 0;
      }
    
    // 丑数列表
      int[]res=new int[index];
      res[0]=1;// 第一个丑数
      int a=0,b=0,c=0;// 三个指针
    // 每次从3个队列中取出一个最小的放入丑数列表中
      for(int i=1;i<index;++i){
          int tempMin=Math.min(res[a]*2,Math.min(res[b]*3,res[c]*5));
          res[i]=tempMin;
          if(tempMin==res[a]*2){
              a++;
          }
          if(tempMin==res[b]*3){
              b++;
          }
          if(tempMin==res[c]*5){
              c++;
          }
      }
      return res[index-1];
    }
    }