LeetCode264 Ugly Number II

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

样例

1
2
3
4
Input:
10
Output:
12

思路

输出第$n$个“丑数”。

不难发现,任意一个“丑数”都是通过其之前某个“丑数”乘2、3或5得到的

那么,我们就可以从初始条件$dp[1] = 1$开始递推出整个“丑数”序列。

1
2
3
4
5
6
7
8
1×2, …

1×3, …

1×5, …

dp[2] = min(dp[1] * 2, dp[1] * 3, dp[1] * 5) = 2;
同时指向“2”的指针右移一格;
1
2
3
4
5
6
7
8
1×2, 2×2, …

1×3, 2×3, …

1×5, 2×5, …

dp[3] = min(dp[2] * 2, dp[1] * 3, dp[1] * 5) = 3;
同时指向“3”的指针右移一格;
1
2
3
4
5
6
7
8
1×2, 2×2, 3×2…

1×3, 2×3, 3×3…

1×5, 2×5, 3×5…

dp[4] = min(dp[2] * 2, dp[2] * 3, dp[1] * 5) = 4;
同时指向“2”的指针右移一格;
1
2
3
4
5
6
7
8
1×2, 2×2, 3×2, 4×2…

1×3, 2×3, 3×3, 4×3…

1×5, 2×5, 3×5, 4×5…

dp[5] = min(dp[3] * 2, dp[2] * 3, dp[1] * 5) = 5;
同时指向“5”的指针右移一格;
1
2
3
4
5
6
7
8
9
10
1×2, 2×2, 3×2, 4×2, 5×2,…

1×3, 2×3, 3×3, 4×3, 5×3,…

1×5, 2×5, 3×5, 4×5, 5×5,…

dp[6] = min(dp[3] * 2, dp[2] * 3, dp[2] * 5) = 6;
注意到此时,dp[3] * 2 和 dp[2] * 3同时取到最小值,
那么,指向“2”的指针和指向“3”的指针应该同时右移一格,
不然得到的序列中将出现重复元素。

以此类推,最终就可以得到答案

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n, 1);
int idx_2 = 0, idx_3 = 0, idx_5 = 0;
for (int i = 1; i < n; ++i) {
dp[i] = min(dp[idx_2] * 2, min(dp[idx_3] * 3, dp[idx_5] * 5));
if (dp[i] == dp[idx_2] * 2) idx_2++;
if (dp[i] == dp[idx_3] * 3) idx_3++;
if (dp[i] == dp[idx_5] * 5) idx_5++;
}
return dp[n - 1];
}
};
分享到 评论