寻找丑数。
题目：我们把只包含因子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;
}
// 用二分法查找第n个丑数
// 对于X，如果X以内的丑数个数是n,而X-1以内的丑数个数是n-1，那么X就是第n个丑数
static long numOfIndex(int n) {
if (n == 1)
return 1;
n--;
long val1 = 1;
int nums1 = 0;
long val2 = 2;
int nums2 = nums235(val2);
while (nums2 < n) {
val1 = val2;
nums1 = nums2;
val2 = val1 * 2;
nums2 = nums235(val2);
}
if (nums1 == n)
return val1;
if (nums2 == n)
return val2;
for (;;) {
long mid = (val1 + val2) / 2;
int nums = nums235(mid);
if (val2 == mid + 1 && nums == n - 1 && nums2 == n)
return val2;
if (mid == val1 + 1 && nums1 == n - 1 && nums == n)
return mid;
if (nums >= n) {
val2 = mid;
nums2 = nums;
} else {
val1 = mid;
nums1 = nums;
}
}
}
public static void main(String[] args) {
method1();
method2();
method3();
method4();
method5();
}
}
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; } // 用二分法查找第n个丑数 // 对于X，如果X以内的丑数个数是n,而X-1以内的丑数个数是n-1，那么X就是第n个丑数 static long numOfIndex(int n) { if (n == 1) return 1; n--; long val1 = 1; int nums1 = 0; long val2 = 2; int nums2 = nums235(val2); while (nums2 < n) { val1 = val2; nums1 = nums2; val2 = val1 * 2; nums2 = nums235(val2); } if (nums1 == n) return val1; if (nums2 == n) return val2; for (;;) { long mid = (val1 + val2) / 2; int nums = nums235(mid); if (val2 == mid + 1 && nums == n - 1 && nums2 == n) return val2; if (mid == val1 + 1 && nums1 == n - 1 && nums == n) return mid; if (nums >= n) { val2 = mid; nums2 = nums; } else { val1 = mid; nums1 = nums; } } } public static void main(String[] args) { method1(); method2(); method3(); method4(); method5(); } }
运行结果（运行时间ms）：
Java代码
193672
93750
33015
16
0
193672 93750 33015 16 0
题后总结：
method4参考于rocketball，lewisw，RStallman
method5参考于taolei0628
该题的最优解为method5。
当然问题还是有的，如果大于long范围时就应该用字符串去处理，但是这个不在算法的考虑之内，因此就不写出处理这个问题的代码了。
那么，到此结题。
Comments | NOTHING