An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return thenthugly number.
Example 1:
**Input:** n = 10
**Output:** 12
**Explanation:** [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.
Example 2:
**Input:** n = 1
**Output:** 1
**Explanation:** 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.
Constraints:
1 <= n <= 1690
ac1: PriorityQueue, or TreeSet
Key: TreeSet can replace PriorityQueue, if not repeated element is allowed.
class Solution {
public int nthUglyNumber(int n) {
TreeSet<Long> ts = new TreeSet<Long>();
ts.add(1l);
for (int i = 1; i < n; i++) {
Long head = ts.pollFirst();
ts.add(head * 2);
ts.add(head * 3);
ts.add(head * 5);
}
return ts.pollFirst().intValue();
}
}
ac2: DP
class Solution {
public int nthUglyNumber(int n) {
int i2 = 0, i3 = 0, i5 = 0;
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; i++) {
dp[i] = Math.min(dp[i2]*2, Math.min(dp[i3]*3, dp[i5]*5));
if (dp[i] == dp[i2]*2) i2++;
if (dp[i] == dp[i3]*3) i3++;
if (dp[i] == dp[i5]*5) i5++;
}
return dp[n-1];
}
}
/**
DP
i 0 1 2 3 4 5 6 7
dp[i] 1 2 3 4 5 6 8 9
i2 2 4 6 8 10 12 18 20
△
i3 3 6 9 12 15 18 27 30
△
i5 5 10 15 20 25 30 45 50
△
**/