题目描述

把只包含质因子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];
}
}