31 lines
975 B
Markdown
31 lines
975 B
Markdown
|
# 49. 丑数
|
|||
|
|
|
|||
|
|
[NowCoder](https://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b?tpId=13&tqId=11186&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github)
|
|||
|
|
|
|||
|
|
## 题目描述
|
|||
|
|
|
|||
|
|
把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。例如 6、8 都是丑数，但 14 不是，因为它包含因子 7。习惯上我们把 1 当做是第一个丑数。求按从小到大的顺序的第 N 个丑数。
|
|||
|
|
|
|||
|
|
## 解题思路
|
|||
|
|
|
|||
|
|
```java
|
|||
|
|
public int GetUglyNumber_Solution(int N) {
|
|||
|
|
if (N <= 6)
|
|||
|
|
return N;
|
|||
|
|
int i2 = 0, i3 = 0, i5 = 0;
|
|||
|
|
int[] dp = new int[N];
|
|||
|
|
dp[0] = 1;
|
|||
|
|
for (int i = 1; i < N; i++) {
|
|||
|
|
int next2 = dp[i2] * 2, next3 = dp[i3] * 3, next5 = dp[i5] * 5;
|
|||
|
|
dp[i] = Math.min(next2, Math.min(next3, next5));
|
|||
|
|
if (dp[i] == next2)
|
|||
|
|
i2++;
|
|||
|
|
if (dp[i] == next3)
|
|||
|
|
i3++;
|
|||
|
|
if (dp[i] == next5)
|
|||
|
|
i5++;
|
|||
|
|
}
|
|||
|
|
return dp[N - 1];
|
|||
|
|
}
|
|||
|
|
```
|