1. 丑数

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

  1. 示例:
  3. 输入: n = 10
  4. 输出: 12
  5. 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

思路：

  • 动态规划
  • 一个丑数 = 更小的丑数 * 某个质因子
  • 用三个指针从索引0位置开始，分别与2，3，5这三个质因子相乘，取最小的数就是下一个索引位置的元素值；该位置数是某个指针乘以质因子得来的，该指针就需要+1
class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n]; // n个长度的数组,存放1~n个丑数
        dp[0] = 1; // 初始化第一个丑数为1
        int a=0,b=0,c=0; // 三个用来辅助质因子相乘的指针
        for(int i=1;i<n;i++){
            int dpa = dp[a]*2,
                dpb = dp[b]*3,
                dpc = dp[c]*5;
            dp[i] = Math.min(Math.min(dpa,dpb),dpc);
            if(dp[i]==dpa) a++;
            if(dp[i]==dpb) b++;
            if(dp[i]==dpc) c++;
        }
        return dp[n-1];
    }
}