【LetMeFly】264.丑数 II
力扣题目链接：https://leetcode.cn/problems/ugly-number-ii/
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1：
输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2：
输入：n = 1
输出：1
解释：1 通常被视为丑数。
提示：
方法一：取最小
开辟一个大小为$n$的数组，第$i$个元素代表第$i$个“丑数”
初始值为：第一个元素是“1”
因为“丑数”的因数中只能包含“2”、“3”、“5”，因此每次分别拿“2”、“3”、“5”去乘某一个“丑数”，最小结果就是下一个“丑数”
乘“丑数”的顺序为：“2”、“3”、“5”相互独立。对于“2”来说，从第一个丑数开始逐渐往后尝试，若为最小则后移。
1
2
3
4
5
6
7
8
| 丑数
1
↑↑↑
235
2 * 1 = 2 ----+
3 * 1 = 3 +---> 最小的是2 * 1 = 2
5 * 1 = 5 ----+
|
👇
1
2
3
4
5
6
7
8
| 丑数
1 2
↑↑ ↑
35 2
2 * 2 = 4 ----+
3 * 1 = 3 +---> 最小的是3 * 1 = 3
5 * 1 = 5 ----+
|
👇
1
2
3
4
5
6
7
8
| 丑数
1 2 3
↑ ↑↑
5 23
2 * 2 = 4 ----+
3 * 2 = 6 +---> 最小的是2 * 2 = 4
5 * 1 = 5 ----+
|
👇
1
2
3
4
5
6
7
8
| 丑数
1 2 3 4
↑ ↑ ↑
5 3 2
2 * 3 = 6 ----+
3 * 2 = 6 +---> 最小的是5 * 1 = 5
5 * 1 = 5 ----+
|
👇
1
2
3
4
5
6
7
8
| 丑数
1 2 3 4 5
↑↑ ↑
35 2
2 * 3 = 6 ----+
3 * 2 = 6 +---> 最小的是2 * 3 = 6和3 * 2 = 6
5 * 2 = 10 ----+
|
👇
1
2
3
4
5
6
7
8
| 丑数
1 2 3 4 5 6
↑ ↑ ↑
5 3 2
2 * 4 = 8 ----+
3 * 3 = 9 +---> 最小的是2 * 4 = 8
5 * 2 = 10 ----+
|
👇
1
2
3
4
| 丑数
1 2 3 4 5 6 8
↑ ↑ ↑
5 3 2
|
每次都会新生成一个丑数。在“2”、“3”、“5”中，哪个数的运算结果等于最小丑数，哪个数的指针就后移一位。
AC代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
int nthUglyNumber(int n) {
vector<int> a(n);
a[0] = 1;
int _2 = 0, _3 = 0, _5 = 0;
int toLoc = 1;
for (int i = 1; i < n; i++) {
int ans2 = a[_2] * 2;
int ans3 = a[_3] * 3;
int ans5 = a[_5] * 5;
int m = min(ans2, min(ans3, ans5));
a[toLoc++] = m;
if (ans2 == m) {
_2++;
}
if (ans3 == m) {
_3++;
}
if (ans5 == m) {
_5++;
}
}
return a[n - 1];
}
};
|
同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126840084