Google Reader

微软面试题之64

by

at 2010-12-03 14:21:54

original http://www.javaeye.com/topic/832545

1. 寻找丑数。
   题目：我们把只包含因子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曾经采用过这道题。 / 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 main(String[] args) {
    method1();
    method2();
    method3();
}

}
运行结果：

192782
94687
30891

      <br><br>
      作者: <a href="http://lyw985.javaeye.com">lyw985</a> 
      <br>
      声明: 本文系JavaEye网站发布的原创文章，未经作者书面许可，严禁任何网站转载本文，否则必将追究法律责任！
      <br><br>
      <span style="color:red">
        <a href="http://www.javaeye.com/topic/832545" style="color:red">已有 <strong>20</strong> 人发表回复，猛击-&gt;&gt;<strong>这里</strong>&lt;&lt;-参与讨论</a>
      </span>
      <br><br><br>

JavaEye推荐

• —软件人才免语言低担保 赴美带薪读研！—