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

每日一题时间: 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

min 动态规划

0 人点赞