题目:我们把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。 求按从小到大的顺序的第1500个丑数。
package com.tech.test; 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 ChouShu2 { 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<Integer> 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<Integer> 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<Integer> list = new ArrayList<Integer>(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):
217897 94913 34201 20 4
该题的最优解为method5。
当然问题还是有的,如果大于long范围时就应该用字符串去处理,但是这个不在算法的考虑之内,因此就不写出处理这个问题的代码了。