前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >(Leetcode 2021 刷题计划) 264. 丑数 II

(Leetcode 2021 刷题计划) 264. 丑数 II

原创
作者头像
windism
修改2021-04-12 10:32:19
2160
修改2021-04-12 10:32:19
举报
文章被收录于专栏:风扬

每日一题时间: 2020-04-11 题目链接: 264. 丑数 II 官方题解链接: 丑数 II

题目

给你一个整数 n ,请你找出并返回第 n 个 丑数 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。

代码语言:txt
复制
示例 1:
输入:n = 10
输出:12
解释:[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2:
输入:n = 1
输出:1
解释:1 通常被视为丑数。

提示:

  • 1 <= n <= 1690

解题方法

动态规划

解题思路: 利用三个指针遍历应当乘以2、3和5的底数,从而不停累积,对于空间可以进行优化,例如针对 min(p2, min(p3, p5)) 之前的空间进行剔除。

代码语言:txt
复制
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> nums(n, 1);
        int p2 = 0, p3 = 0, p5 = 0;
        for (int i = 1; i < n; ++i) {
            int n2 = nums[p2] * 2;
            int n3 = nums[p3] * 3;
            int n5 = nums[p5] * 5;
            nums[i] = min (n2, min(n3, n5));
            if (nums[i] == n2) ++p2;
            if (nums[i] == n3) ++p3;
            if (nums[i] == n5) ++p5;
        }
        return nums.back();
    }
};
  • 复杂度分析
    • 时间复杂度: O(N)
    • 空间复杂度: O(N)

参考资料

  1. 264. 丑数 II
  2. 丑数 II

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
  • 解题方法
    • 动态规划
    • 参考资料
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档