微软面试题之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范围时就应该用字符串去处理，但是这个不在算法的考虑之内，因此就不写出处理这个问题的代码了。
那么，到此结题。

感觉或许可以直接利用2,3,4,5根据创建数学方城，非常简单的求值

从1 到 30刚好是一个周期，
1 = 2的0次+3的0次+5的0次
30 = 2的1次+3的1次+5的1次
当中有18个数，
1500/18 = 83余6
那就是2的83次+3的83次+5的83次，在向上递增6个就是了

晕，好像这个周期不对

你想得太简单的，计算机遍历的答案是859963392

那你前面的三个数字那么来的，我遍历了下也是859963392
还有你的几种方法我运行了下，很长时间没有算出答案，即使算出来，你的时间复杂度也要在n*nlgn了

	private static List<Integer> ugly = new ArrayList<Integer>();

	public static void main(String[] args) {
		Ugly.ugly.add(1);
		Ugly.ugly.add(2);
		Ugly.ugly.add(3);
		int max = 3;
		System.out.println(System.currentTimeMillis());
		while (true) {
			int m2 = 0;
			for (Integer i : ugly) {
				m2 = i * 2;
				if (m2 > max)
					break;
			}
			int m3 = 0;
			for (Integer i : ugly) {
				m3 = i * 3;
				if (m3 > max)
					break;
			}
			int m5 = 0;
			for (Integer i : ugly) {
				m5 = i * 5;
				if (m5 > max)
					break;
			}
			max=(m2<m3?m2:m3)<m5?(m2<m3?m2:m3):m5;
			Ugly.ugly.add(max);
			if(Ugly.ugly.size()==1500){
				System.out.println(max);
				break;
			}
		}
		System.out.println(System.currentTimeMillis());
	}

大概花费0.2秒

支持，有时间了可以整理个合集或者系列，这样大家就有练手的材料了，呵呵

是没有周期的，不过还是可以生成

public class Question64 {

    private static int getUglyDigit(int number) {

        long l = System.currentTimeMillis();

        int[] uglies = new int[number];

        uglies[0] = 1;

        for (int i = 1; i < number; i ++) {

            int m2 = getMaxN(uglies, i, 2);
            int m3 = getMaxN(uglies, i, 3);
            int m5 = getMaxN(uglies, i, 5);
            
            uglies[i] = Math.min(m5, Math.min(m2, m3));
        }

        System.out.println(System.currentTimeMillis() - l);
        return uglies[number-1];
    }

    private static int getMaxN(int[] uglies, int count, int n) {
        /**
         * 这个用二分定位或许更快，也更稳定
         */
        for (int i = 0; i < count; i ++) {
            if (uglies[i] * n > uglies[count-1]) return uglies[i] * n;
        }
        return 0;
    }

    public static void main(String[] args) {

        System.out.println(getUglyDigit(1501));

    }
}

输出
0
860934420
几乎不用时间

2^a*3^b*5^c???贪心算法？

用二分定位的话 应该作到极限了
当然也有可能数学NB的人 直接给出数值解 ^_^

微软还招搞java的？