每日题解:LeetCode 264. 丑数 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 通常被视为丑数。
           

解法

class Solution {
    public int nthUglyNumber(int n) {
     int [] dp= new int[n+1];
     dp[1]=1;
     int p2=1,p3=1,p5=1;
        for(int i=2;i<=n;i++){
            int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
            dp[i] = Math.min(Math.min(num2, num3), num5);
                if(dp[i]==num2){
                p2++;
                }
                if(dp[i]==num3){
                    p3++;
                }
                if(dp[i]==num5){
                p5++;
                }
        }
     return dp[n];
    }
}
           

解题思路

动态规划

丑数指的是由只包含质因数

2

、

3

和/或

5

的正整数。题目找到有序的第n个丑数，比如

[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]
           

依次生成丑数，然后存入最小堆进行排序

int[] factors = {2, 3, 5};
for (int factor : factors) {
long next = curr * factor;
}
           

使用小顶堆的方法是先存再排，但是，存在重复计算的问题，时间和空间复杂度都比较高，所以使用动态规划

我们先模拟手写丑数的过程

由1 开始，1 乘 2, 1 乘 3 ,1 乘 5

数组为

{1,2,3,5}

再到2，2 乘 2， 2 乘 3 ;2 乘 5

数组为

{1,2,3,4,5,6,10}

所以，使用动态规划进行

先排再存

• 我们需要定义 3 个指针 p2, p3, p5,代表的是第几个数的2倍、第几个数 3 倍、第几个数 5 倍
• 然后每次新的丑数 dp[i] = min(dp[p2 * 2, dp[p3 * 3, dp[p5 * 5)
• 然后根据 dp[i] 是由 p2,p3,p5哪个相乘得到的，对应的指针 + 1,继续寻找还未计算到丑数

for(int i=2;i<=n;i++){
          int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
           dp[i] = Math.min(Math.min(num2, num3), num5);
            if(dp[i]==num2){
               p2++;
            }
            if(dp[i]==num3){
                p3++;
            }
            if(dp[i]==num5){
               p5++;
            }
     }