每日题解: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];
    }
}

解题思路

动态规划

丑数指的是由只包含质因数 23 和/或 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++;
            }
     }
最近的文章

每日题解:LeetCode 179. 最大数

题目地址题目描述给定一组非负整数nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。示例1:输入:nums=[10,2]输出:"210"示例2:输入:nums=[3,30,34,5,9]输出:&qu…

继续阅读
更早的文章

每日题解:LeetCode 33. 搜索旋转排序数组

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/题目描述已知一个长度为n的数组,预先按照升序排列,经由1到n次旋转后,得到输入数组。例如,原数组nums=[0,1,2,4,5,6,7]在变化后可能得到:若旋转4次,则可以…

继续阅读