鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > erlang > >

剑指offer(二十八)之丑数

来源:互联网 作者:佚名 时间:2016-05-23 10:23
题目描述 把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。 思路分析: 1.首先,丑数都是由前5个 丑数1,2,3,4,5乘以因子2,3,5才得到

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

思路分析:

1.首先,丑数都是由前5个丑数1,2,3,4,5乘以因子2,3,5才得到的。

2.这里将得到的丑数都存放在数组中。分析一下得到第6个丑数的过程,其他丑数类比。

3.1 将前5个丑数乘以2,然后与第5个丑数进行比较,找出第一个乘以2大于第5个丑数的丑数,将其放在min2中。

3.2 将前5个丑数乘以3,然后与第5个丑数进行比较,找出第一个乘以3大于第5个丑数的丑数,将其放在min3中。

3.3 将前5个丑数乘以5,然后与第5个丑数进行比较,找出第一个乘以5大于第5个丑数的丑数,将其放在min5中。

4.经过上述,第6个丑数必然是min2,min3,min5中最小的那个丑数。比较这三个数,就可以得到第6个丑数。

代码:

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index<=0){
            return 0;
        }
        if(index<=5){
            return index;
        }
        int []arrays=new int[index];
        arrays[0]=1;
        arrays[1]=2;
        arrays[2]=3;
        arrays[3]=4;
        arrays[4]=5;
        int min=0,temp=0;
        int min2=0,min3=0,min5=0;
        for(int i=5;i<index;i++)
        {
            for(int j=0;j<i;j++)
            {
                temp=arrays[j]*2;
           		if(temp>arrays[i-1])
                {
                    min2=temp;
                    break;
                }
            }
            for(int k=0;k<i;k++)
            {
                temp=arrays[k]*3;
           		if(temp>arrays[i-1])
                {
                    min3=temp;
                    break;
                }
            }
            for(int z=0;z<i;z++)
            {
                temp=arrays[z]*5;
           		if(temp>arrays[i-1])
                {
                    min5=temp;
                    break;
                }
            }
            min=min2>min3?(min3>min5?min5:min3):(min2>min5?min5:min2);
            arrays[i]=min;
        }
        return arrays[index-1];
    }
}



网友评论
<