程序员人生网站导航

丑数

栏目：php教程时间：2016-08-05 12:53:18

题目

把只包括因子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);
    }

}

------分隔线----------------------------

上一篇 解释器模式(Interpreter)

下一篇 仿百度地图街景实现

------分隔线----------------------------