国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > 丑数

丑数

来源:程序员人生   发布时间:2016-08-05 12:53:18 阅读次数:1164次

题目

把只包括因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,由于它包括因子7。 习惯上我们把1当作是第1个丑数。求按从小到大的顺序的第N个丑数。

解题

暴力的不说了
1个数只能是2、3、5因子组成是丑数
丑数M,1定是由于前面的数乘以2、3、5后选取的最小值
所有可以定义1个数组寄存丑数,当时第i个丑数的时候,将前面的i⑴个丑数分别乘以2、3、5选取最小值(并且不是前面i⑴个丑数)就是第i个丑数
下面程序超时了

import java.util.*; public class Solution { public int GetUglyNumber_Solution(int index) { ArrayList<Integer> u = new ArrayList<Integer>(); u.add(0); u.add(1); if(index == 1) return u.get(index); int preIndex = 2; while(preIndex <= index){ int preU = Integer.MAX_VALUE; for(int i=1;i<u.size() ;i++){ int ui = u.get(i); if(!u.contains(ui*2)) preU = Math.min(preU,ui*2); if(!u.contains(ui*3)) preU = Math.min(preU,ui*3); if(!u.contains(ui*5)) preU = Math.min(preU,ui*5); } u.add(preU); preIndex ++; } return u.get(index); } }

判断是不是已存在、找到最小值时间复杂度都是比较高的
在找下1个丑数时候,尽心了许多重复计算
计算M丑数,只与N有关,而与小于N的无关
而这个N应当包括:N2、N3、N5这3个数,我们只要找到这3个数就行了,这需要3个指针了,3个指针指向不同的N,选取这个N后,其指针后移1位
这个和书上讲的很类似,我只是换了1个角度理解,重点是上面的方法让我很容易想到了这个方法

import java.util.*; public class Solution { public int GetUglyNumber_Solution(int index) { ArrayList<Integer> u = new ArrayList<Integer>(); u.add(0); u.add(1); if(index == 1) return u.get(index); int i1 = 1; int i2 = 1; int i3 = 1; int preIndex = 2; while(preIndex <= index){ int preU = Integer.MAX_VALUE; int u1 = u.get(i1) * 2; int u2 = u.get(i2) * 3; int u3 = u.get(i3) * 5; preU = Math.min(preU,u1); preU = Math.min(preU,u2); preU = Math.min(preU,u3); if(preU == u1){ i1++; } if(preU == u2){ i2++; } if(preU == u3){ i3++; } u.add(preU); preIndex ++; } return u.get(index); } }

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生