题目信息
-
时间： 2019-07-03
-
题目链接：Leetcode
-
tag：动态规划 小根堆
-
难易程度：中等
-
题目描述：
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
注意
1. 1是丑数
2. n < 1690
解题思路
本题难点
丑数的定义以及查找的方式
具体思路
丑数只包含因子 2,3,5 ，因此有 “丑数 = 某较小丑数 × 某因子” （例如：10=5×2）
设已知长度为 n 的丑数序列 x1,x2,⋯,xn ，求第 n+1 个丑数 xn+1 。根根据递推性质，丑数 x n+1 只可能是以下三种情况其中之一（索引 a,b,c 为未知数）：
由于 x n+1 是 最接近 x n的丑数，因此索引 a,b,c 需满足以下条件：
若索引 a,b,c 满足以上条件，则可使用递推公式计算下个丑数 xn+1 ，其为三种情况中的最小值，
即：xn+1=min(xa × 2, xb × 3, xc × 5)
动态规划思想：
-
状态定义：设动态规划列表 dp ，dp[i] 代表第 i+1 个丑数。
-
转移方程：每轮计算 dp[i] 后，需要更新索引 a,b,c 的值，使其始终满足方程条件。实现方法：分别独立判断 dp[i] 和 dp[a]×2 , dp[b]×3 , dp[c]×5 的大小关系，若相等则将对应索引 a,b,c 加 1 。
注意: dp[0]=1，第一个丑数为 1 ；
代码
class Solution {
public int nthUglyNumber(int n) {
int a = 0, b = 0, c = 0;
int[] dp = new int[n];
//第一个丑数为 1
dp[0] = 1;
for(int i = 1 ; i < n ; i++){
int n2 = 2 * dp[a];
int n3 = 3 * dp[b];
int n5 = 5 * dp[c];
dp[i] = Math.min(Math.min(n2,n3),n5);
if(dp[i] == n2){
a++;
}
if(dp[i] == n3){
b++;
}
if(dp[i] == n5){
c++;
}
}
return dp[n-1];
}
}
复杂度分析：
- 时间复杂度 O(N) ： 其中 N=n ，动态规划需遍历计算 dp列表。
- 空间复杂度 O(N) ： 长度为 N 的 dp 列表使用 O(N)的额外空间。
其他优秀解答
解题思路
小根堆，要去找第n个丑数，首先想到的就是一个个去生成。uglyNum=2^x ∗3^y ∗5^z ，由 1 生成了 2、3、5 ，接着 2、3、5 利用前面公式继续生成。生成过程是先放小的，并且我们需要去重，去重就需要用到 set
代码
class Solution {
public int nthUglyNumber(int n) {
//小根堆
PriorityQueue<Long> pq = new PriorityQueue<>();
Set<Long> s = new HashSet<>();
//初始化,放进堆和set，发现1要开Long数组才可以
long[] primes = new long[]{2, 3, 5};
for (long prime : primes) {
pq.offer(prime);
s.add(prime);
}
long num = 1;
for (int i = 1; i < n; i++) {
num = pq.poll();
//遍历三个因子
for (int j = 0; j < 3; j++) {
if (!s.contains(num * primes[j])) {
pq.offer(num * primes[j]);
s.add(num * primes[j]);
}
}
}
return (int) num;
}
}