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];}
}