每日一题时间:
2020-04-11
题目链接: 264. 丑数 II 官方题解链接: 丑数 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 通常被视为丑数。
提示:
1 <= n <= 1690
解题思路: 利用三个指针遍历应当乘以2、3和5的底数,从而不停累积,对于空间可以进行优化,例如针对 min(p2, min(p3, p5))
之前的空间进行剔除。
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)
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。