【4.11】LeetCode每日一题· 丑数II

2021年04月11日 13时01分

标签： LeetCode 动态规划数学堆

## 题目描述
给你一个整数**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 通常被视为丑数。
```

#### 提示
```
1 <= n <= 1690
```

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/ugly-number-ii/ "题目链接")

## 解题思路
### 最小堆
对于某一个丑数`i`，`i*2`、`i*3`、`i*5`也一定是丑数。因此可以维护一个最小堆，堆中从小到达存储所有的丑数：
1. 由于**1**是最小的丑数，因此首先将**1**存入堆中；
2. 每次从堆中取最小元素`i`，并将`i*2`、`i*3`、`i*5`插入堆中
3. 那么第`n`次取得的元素就是第`n`个丑数

#### 代码
```cpp
class Solution {
public:
    int nthUglyNumber(int n) {
        set<long long> heap;
        heap.insert(1);
        long long top;
        while(--n){
            top = *heap.begin();
            heap.erase(top);
            heap.insert(top*2);
            heap.insert(top*3);
            heap.insert(top*5);
        }
        return *heap.begin();
    }
};
```

#### 用时和内存
> 执行用时：152 ms，在所有 C++提交中击败了13.71%的用户
> 内存消耗：28.9 MB，在所有 C++提交中击败了10.73%的用户

### 动态规划
在最小堆的解法中，维护最小堆的时间复杂度为对数级，同时堆中需要保存超过`n`个丑数，因此时间复杂度、空间复杂度均较高。可以考虑使用动态规划求解。

设`dp[i]表示第i个丑数`，那么`dp[n]`就是第n个丑数。

维护三个指针`p2`、`p3`、`p5`，表示下一个丑数可能为当前指针指向的丑数与对应质因数的值，那么对于$$2\leq i \leq n$$，有

```math
dp[i] = \min(dp[p2]*2, dp[p3]*3, dp[p5]*5)
```

同时，对于`dp[i]`确实取到的那一个**或多个值**（由于`dp[p2]*2`、`dp[p3]*3`或者`dp[p5]*5`可能有值相同的情况，所以可能`dp[i]`对应这三个值中的多个值），需要将对应的指针加1。

正确性证明见[LeetCode官方题解](https://leetcode-cn.com/problems/ugly-number-ii/solution/chou-shu-ii-by-leetcode-solution-uoqd/)。

#### 代码
```cpp
class Solution {
public:
    int nthUglyNumber(int n) {
        long long dp[n+1];
        int p2 = 1, p3 = 1, p5 = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            dp[i] = min(min(dp[p2]*2, dp[p3]*3), dp[p5]*5);
            if(dp[i] == dp[p2]*2){
                p2++;
            }
            if(dp[i] == dp[p3]*3){
                p3++;
            }
            if(dp[i] == dp[p5]*5){
                p5++;
            }
        }
        return dp[n];
    }
};
```

#### 用时和内存
> 执行用时：0 ms，在所有 C++提交中击败了100.00%的用户
> 内存消耗：5.8 MB，在所有 C++提交中击败了96.16%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【4.11】LeetCode每日一题· 丑数II

所有评论

暂无评论

新增评论