Day20：丑数

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

说明：丑数是只包含质因数 2、3 和/或 5 的正整数；1 是丑数。

示例 1：

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

 LCR 168. 丑数 - 力扣（LeetCode）

 首先使用最小堆来做这个题目，因为2，3，5是丑数，那么2x,3x,5x也是丑数，我们使用一个set去重就行了。排序的话堆会帮我们排序排好的。

第一遍的代码生成丑数的方式不对：

class Solution {
    public int nthUglyNumber(int n) {
        int ugly = 0;
        if(n == 1){
            return 1;
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        HashSet<Integer> hashSet = new HashSet<>();
        for(int i = 1; i < n; i++){
            hashSet.add(2*i);
            hashSet.add(3*i);
            hashSet.add(5*i);
        }

        for(Integer i : hashSet){
            minHeap.offer(i);
        }

        int index = 0;
        for (Integer i : minHeap) {
            if (index == n) {
                ugly = i;
                break;
            }
            index++;
        }

        return ugly;
    }
}

比如14加进去了，但是14不是丑数。

应该这样，把1加进去，然后，1的2，3，5倍加进去，然后1出队，就这样一直出队并把堆顶的2，3，5倍加入，用一个Set接收，如果成功接收，index++，等index等于n的时候，返回。

第二版代码符合逻辑，但是在n过大的时候超出时间限制：

class Solution {
    public int nthUglyNumber(int n) {
        int index = 0;
        int result = 0;
        if(n == 1){
            return 1;
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        HashSet<Integer> hashSet = new HashSet<>();
       
        minHeap.offer(1);
        while(!minHeap.isEmpty()){
            int top = minHeap.poll();
            minHeap.offer(top*2);
            minHeap.offer(top*3);
            minHeap.offer(top*5);

            if(hashSet.add(top)){
                index++;
            }

            if(index == n){
                result = top;
                break;
            }
        }
        return result;
    }
}

想要再优化，只能上动态规划了。

dp[i] 代表第i个丑数，dp[1] = 1; 设置三个指针p2,p3,p5用来代表当前元素乘以几，dp[i] = min(dp[p2]*2,dp[p3]*3,dp[p5]*5),如果使用了指针，就得++；

最后return dp[n];

class Solution {
    public int nthUglyNumber(int n) {
       int[] dp = new int[n+1];
       dp[1] = 1;
       int p2 = 1;
       int p3 = 1;
       int p5 = 1;
       for(int i = 2;i < n+1; i++){
          dp[i] = Math.min(Math.min(dp[p2]*2,dp[p3]*3),dp[p5]*5);
          if(dp[i] == dp[p2]*2){
            p2++;
          }

          if(dp[i] == dp[p3]*3){
            p3++;
          }

          if(dp[i] == dp[p5]*5){
            p5++;
          }
       }
       return dp[n];
    }
}