[zz]微软面试题之64

64. 寻找丑数。 
题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。 求按从小到大的顺序的第1500个丑数。 
分析：这是一道在网络上广为流传的面试题，据说google曾经采用过这道题。 

package microsoft;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 64. 寻找丑数。<br/>
 * 题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数， 但14不是，因为它包含因子7。<br/>
 * 习惯上我们把1当做是第一个丑数。 求按从小到大的顺序的第1500个丑数。<br/>
 * 分析：这是一道在网络上广为流传的面试题，据说google曾经采用过这道题。<br/>
 * 总结:<br/>
 * 1.method1是最基础的遍历，唯一的优点估计就是简单易懂。<br/>
 * 2.method2,method3的思想是先人工估算范围值，将一定范围内的值乘2，3，5排重增加，不同的地方在于method2重新遍历，
 * method3排序求下标<br/>
 * 3.method4的思想是将已经获取的值分别遍历，乘以2，3，5，当比最大值大就停止，比较这3个数的最小值，增加到定义的有序数组中。<br/>
 * 4.method5的思想是将数进行评估，评估出该数包含丑数的数量，当超过丑数要求数量时，进行2分法进行缩小范围，直至求出解。
 */
public class Question64 {
    private static int num = 1500;

    /**
     * 最基础的方法
     */
    public static void method1() {
        long l = System.currentTimeMillis();
        long temp;
        int time = 0;
        for (long i = 1;; i++) {
            temp = i;
            while (temp % 2 == 0) {
                temp /= 2;
            }
            while (temp % 3 == 0) {
                temp /= 3;
            }
            while (temp % 5 == 0) {
                temp /= 5;
            }
            if (temp == 1) {
                time++;
                // System.out.println(time + ":" + i);
                if (time == num) {
                    break;
                }
            }
        }
        System.out.println(System.currentTimeMillis() - l);
    }

    public static void method2() {
        // 初始化
        long l = System.currentTimeMillis();
        Set set = new HashSet<Integer>();
        set.add(1);
        for (int i = 1; i < Integer.MAX_VALUE / 5; i++) {
            if (set.contains(i)) {
                set.add(2 * i);
                set.add(3 * i);
                set.add(5 * i);
            }
        }
        // 遍历
        int time = 0;
        for (int i = 1; i < Integer.MAX_VALUE; i++) {
            if (set.contains(i)) {
                time++;
                // System.out.println(time + ":" + i);
                if (time == num) {
                    break;
                }
            }
        }
        System.out.println(System.currentTimeMillis() - l);
    }

    public static void method3() {
        // 初始化
        long l = System.currentTimeMillis();
        Set set = new HashSet<Integer>();
        set.add(1);
        for (int i = 1; i < Integer.MAX_VALUE / 5; i++) {
            if (set.contains(i)) {
                set.add(2 * i);
                set.add(3 * i);
                set.add(5 * i);
            }
        }
        // 排序
        List list = new ArrayList(set);
        Collections.sort(list);
        // System.out.println(list.get(1499));
        System.out.println(System.currentTimeMillis() - l);
    }

    public static void method4() {
        long l = System.currentTimeMillis();
        int[] ints = new int[num];
        ints[0] = 1;
        for (int count = 1, m2 = 0, m3 = 0, m5 = 0; count < num; count++) {
            for (int i = 0; i < count; i++) {
                if (ints[i] * 2 > ints[count - 1]) {
                    m2 = ints[i] * 2;
                    break;
                }
            }
            for (int i = 0; i < count; i++) {
                if (ints[i] * 3 > ints[count - 1]) {
                    m3 = ints[i] * 3;
                    break;
                }
            }
            for (int i = 0; i < count; i++) {
                if (ints[i] * 5 > ints[count - 1]) {
                    m5 = ints[i] * 5;
                    break;
                }
            }
            ints[count] = Math.min(m2, Math.min(m3, m5));
        }
        System.out.println(System.currentTimeMillis() - l);
    }

    public static void method5() {
        long l = System.currentTimeMillis();
        long varR = 1, varL = 0;
        while (nums235(varR) < num) {
            varL = varR;
            varR *= 2;
        }
        while (varL + 1 != varR) {
            long mid = (varL + varR) / 2;
            if (nums235(mid) >= num) {
                varR = mid;
            }
            if (nums235(mid) < num) {
                varL = mid;
            }
        }
        System.out.println(System.currentTimeMillis() - l);
    }

    static int nums235(long val) {
        if (val < 1)
            return 0;
        int n = 1;// 加上1
        while (val >= 2) {
            n += 1 + nums35(val);
            val /= 2;
        }
        return n;
    }

    static int nums35(long val) {
        int n = 0;
        while (val >= 3) {
            n += 1 + nums5(val);
            val /= 3;
        }
        return n;
    }

    static int nums5(long val) {
        int n = 0;
        while (val >= 5) {
            n++;
            val /= 5;
        }
        return n;
    }

    public static void main(String[] args) {
        method1();
        method2();
        method3();
        method4();
        method5();
    }

}

运行结果（运行时间ms）： 

193672
93750
33015
16
0

题后总结： 
感谢rocketball，lewisw，RStallman，taolei0628对该题的技术支持。 

method4参考于rocketball，lewisw，RStallman 
method5参考于taolei0628 

该题的最优解为method5。 

当然问题还是有的，如果大于long范围时就应该用字符串去处理，但是这个不在算法的考虑之内，因此就不写出处理这个问题的代码了。 
那么，到此结题。 
http://www.iteye.com/topic/832545