首页 > 代码库 > find the Ugly Number
find the Ugly Number
题目描述
把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
反思：我发现有些题目，你如果不是之商超群的那一类人，如果不经过大量的训练是很难做出来的(也可能是自己智商该充值了。。。。)，把刷题当成一种习惯吧
这道题，刚开始看到，一时什么思路都没有，想了好久才想到， 依次反复除以2 3 5最后等于0就说明是丑数。实现之后一直显示超时，凭借我之前微少的经验，判断自己是程序出问题了。。。找疯了找不到bug，后来看讨论，发现原来牛课网把这种做法卡了，所以只能找一个更优良的，时间复杂度更低的做法。于是又用到了动态规划
dp[i](第i个丑数)=max(dp[k2]*2(第一个dp[n]*2大于dp[i-1]的那个丑数),dp[k3]*3(第一个dp[n]*3大于dp[i-1]的那个丑数),dp[k5]*5(第一个dp[n]*5大于dp[i-1]的那个丑数),
基本思想是：后面的丑数一定是前边的某一个丑数乘以 2 或者3 或者5得到的，而且这个时尽可能小的那个，所以先找到所有的丑数乘以2之后结果刚好大于目前最大的丑数的那个位置，记为k2， 同样找到所有乘以3正好大于目前最大丑数的那个位置记为k3，再找到k5，这时i++在一直和 这三个位置的丑数分别乘以2 3 5的结果作对比，如果此时i等于某一个了，那说明下一次 那个k2或者k3或者k5相应后移，再求。。。。
上代码
import java.util.*;import java.lang.*;public class Solution { public int GetUglyNumber_Solution(int index) { if(index<7)return index; int[] dp=new int[index+1]; dp[1]=1; int mid2=1,mid3=1,mid5=1,i; for(i=2;i<index+1;i++){ dp[i]=Math.min(dp[mid2]*2,Math.min(dp[mid3]*3,dp[mid5]*5)); if(dp[mid2]*2==dp[i]) mid2++; if(dp[mid3]*3==dp[i]) mid3++; if(dp[mid5]*5==dp[i]) mid5++; } return dp[index]; } }
find the Ugly Number
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。