题目信息
LeetoCode地址: . - 力扣（LeetCode）
题目理解
所谓丑数就是满足: (2^x)*(3^y)*(5^z), 其中,x,y,z >= 0的数。
题目要求的是求严格递增的第n个丑数。
最小堆写法
可以维护一个小顶堆，每一次拿出堆顶元素，然后分别乘以2，3，5再都扔回堆里，依次进行操作，直到第n个元素。在实现时，要注意对重复元素的处理。
时间复杂度:(nlogn),堆的每次出入操作需要花费logn, 共需要n次这样的操作。
额外空间复杂度: (n)， 我们需要维护一个最大长度为n的堆。
class Solution {
public int nthUglyNumber(int n) {
int[] factors = {2, 3, 5};
Set<Long> seen = new HashSet<Long>();
PriorityQueue<Long> heap = new PriorityQueue<Long>();
seen.add(1L);
heap.offer(1L);
int ugly = 0;
for (int i = 0; i < n; i++) {
long curr = heap.poll();
ugly = (int) curr;
for (int factor : factors) {
long next = curr * factor;
if (seen.add(next)) {
heap.offer(next);
}
}
}
return ugly;
}
}动态规划写法
第k个丑数一定是它之前的0到k-1之间某一个更小的的丑数乘以2或3或5得到的，我们要找的就是其中乘完后刚好最小，同时又大过k-1丑数的数。
既然如此，可以使用三个下标x,y,z分别记录还未被2，3，5乘过的丑数。
每一次计算第k个丑数时，将第x个丑数乘以2，第y个丑数乘以3，第z个丑数乘以5，得到的最小值就是第k个丑数。假设第x个丑数乘以2是最小的，则将x+1,因为第x个丑数已经乘过2并用过了。y和z类似。
时间复杂度: O(n)
空间复杂度: O(n)
static int[] dp = new int[1691];
public int nthUglyNumber(int n) {
if (dp[0] == 0) {
dp[1] = 1;
int x=1,y=1,z=1;
for (int i = 2; i<=n; i++) {
int xMin = dp[x] *2;
int yMin = dp[y] *3;
int zMin = dp[z] * 5;
int min = Math.min(xMin, Math.min(yMin, zMin));
if (min == xMin) {
x++;
}
if (min == yMin) {
y++;
}
if (min == zMin) {
z++;
}
dp[i] = min;
}
}
return dp[n];
}