Leetcode 264. 丑数 II （数论，三指针，类dp）
Leetcode 264. 丑数 II （数论，三指针，类dp）
glm233
发布于 2020-09-28 14:50:52
发布于 2020-09-28 14:50:52
编写一个程序，找出第 n 个丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。说明:
1是丑数。n不超过1690。
这道题暴力会超时，所以换种方法：三指针法
具体而言是指置三指针index2,index3,index5,比方说当前要求的是第i个丑数，我们已经知道前i-1个丑数，这一定是从这前i-1个丑数中产生的，初始时index2=index3=index5=1，指在1这个数的下标（我们设下标是1）
一开始，丑数只有{1}，1可以同2，3，5相乘，取最小的1×2=2添加到丑数序列中。
现在丑数中有{1，2}，在上一步中，1已经同2相乘过了，所以今后没必要再比较1×2了，我们说1失去了同2相乘的资格。
现在1有与3，5相乘的资格，2有与2，3，5相乘的资格，但没必要，所以index3，index5下标不移动，还是1这个数的位置
然后取2作为第二个数，index2++，指针移动，以此类推，只要被取到就移动直到我们求得了n个数
class Solution {
public int nthUglyNumber(int n) {
int index2=0,index3=0,index5=0,k=1;
int []ans=new int[n];
ans[0]=1;
while(k<n)
{
ans[k]=Math.min(ans[index2]*2,Math.min(ans[index3]*3,ans[index5]*5));
if(ans[index2]*2==ans[k])index2++;
if(ans[index3]*3==ans[k])index3++;
if(ans[index5]*5==ans[k])index5++;
k++;
}
return ans[n-1];
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-04-02 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读