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

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

题目

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

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

提示：

• 1 <= n <= 1690

解题方法

动态规划

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

• 复杂度分析
  • 时间复杂度: O(N)
  • 空间复杂度: O(N)

参考资料

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