微软面试题之64

回楼上的，就速度而言，你的是比我好的  ^_^

我现在看万能不能分析的出来 为啥结果不一致

问题查出来了，是matlab的问题。。。。 matlab对double类型的数据作了优化
可以跑的快
但是double类型的运算会有误差 在第8939个数时，一个书乘以5得出来一个很奇怪的结果
看来matlab在作大的数据分析的时候 还是得小心

而当我吧数据类型都换成uint32计算的时候
matlab就是蜗牛了。。

赞，这应该是我碰上的最好的解决方案了，拜服

2^0 * 3^0 * 5^0
2^1 * 3^0 * 5^0
2^1 * 3^1 * 5^0
2^1 * 3^1 * 5^1
2^2 * 3^1 * 5^1
2^2 * 3^2 * 5^1
2^2 * 3^2 * 5^2
2^3 * 3^2 * 5^2
2^3 * 3^3 * 5^2
2^3 * 3^3 * 5^3

从这个规律看，第1500个数应该是：
2^500 * 3^500 * 5^499

这个可以直接遍历啊，已有的数*2、*3、*5，每次从中挑出最小的加入列表（不容许重复），时间也挺快的。

public class FineNum {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub		
		long t1 = System.currentTimeMillis();		
		int num = 1500;
		int index = 1;
		long []m = new long[num];
		int i2 = 0;
		int i3 = 0;
		int i5 = 0;
		m[0] = 1;
		long a = m[i2] * 2;
		long b = m[i3] * 3;
		long c = m[i5] * 5;
		while(index < num){			
			int r = a < b? a < c? 2 : 5 : b < c? 3 : 5;
			switch(r){
			case 2:
				if(m[index - 1] != a){
					m[index ++ ] = a;									
				}
				i2 ++;
				a = m[i2] * 2;
				break;
			case 3:
				if(m[index - 1] != b){
					m[index ++ ] = b;									
				}
				i3 ++;
				b = m[i3] * 3;
				break;
			case 5:
				if(m[index - 1] != c){
					m[index ++ ] = c;									
				}
				i5 ++;
				c = m[i5] * 5;
				break;
			default:				
				System.out.println("wrong!");			
			}
		}
		System.out.println(m[num-1]);
		long t2 = System.currentTimeMillis();
		System.out.println("time:"+(t2 - t1));

	}

}

 执行结果：（时间单位：ms）

859963392
time:0

计算第10000个丑数，执行结果：

288325195312500000
time:5

计算第15000个时，超出long的表示范围

算错了，漏了不少数，应该是
X^3 = 1500
X在11到12之间

最后应该是：
2^12 * 3^12 * 5^8

 

这个方法跟method4方法一致，改进的地方在于记录了上次被选中的下标，确实有提升效率的功能

public class Question64 {

    private static long getUglyDigit(int number) {

        /**
         * 不仅仅记录当前获得的丑数值，同时记录当前丑数是由前面第几个丑数及乘上几获得的。
         *
         */
        long[][] uglies = new long[number][3];

        uglies[0] = new long[]{1, -1, -1};
        uglies[1] = new long[]{2, 0, 2};
        uglies[2] = new long[]{3, 0, 3};
        uglies[3] = new long[]{4, 1, 2};
        uglies[4] = new long[]{5, 0, 5};
        uglies[5] = new long[]{6, 1, 3};
        uglies[6] = new long[]{8, 3, 2};
        uglies[7] = new long[]{9, 2, 3};
        uglies[8] = new long[]{10, 1, 5};

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

            long[] m2 = getMaxN(uglies, i, 2);
            long[] m3 = getMaxN(uglies, i, 3);
            long[] m5 = getMaxN(uglies, i, 5);

            if (m2[0] <= m3[0] && m2[0] <= m5[0]) {

//                uglies[i] = m2;
                uglies[i][0] = m2[0];
                uglies[i][1] = m2[1];
                uglies[i][2] = m2[2];

            } else if (m3[0] <= m2[0] && m3[0] <= m5[0]) {

//                uglies[i] = m3;
                uglies[i][0] = m3[0];
                uglies[i][1] = m3[1];
                uglies[i][2] = m3[2];

            } else {

//                uglies[i] = m5;
                uglies[i][0] = m5[0];
                uglies[i][1] = m5[1];
                uglies[i][2] = m5[2];
            }
        }

        System.out.println(number + ":" + uglies[number - 1][0]);
        return uglies[number - 1][0];
    }

    private static long[] getMaxN(long[][] uglies, int count, int n) {

        for (int i = count; i > 0; i --) {
           
            int sIndex = (int) (uglies[i - 1][1] + 1);
           
            if (uglies[i - 1][2] == n) {
               
                for (int l = sIndex; l < count; l ++) {
                   
                    if (n * uglies[l][0] > uglies[count - 1][0]) {
                       
                        return new long[]{n * uglies[l][0], l, n};
                    }
                }
            }
        }

        return new long[]{};
    }

    public static void main(String[] args) {

        long t = System.currentTimeMillis();

        getUglyDigit(100);
        getUglyDigit(1000);
        getUglyDigit(1500);
        getUglyDigit(5000);
        getUglyDigit(9918);
        getUglyDigit(10000);
       
        System.out.println("used time " + (System.currentTimeMillis() - t) + " ms.");
    }
}

还是这个最快，最简单，正解

adoda的算法确实很好，是我一开始就想当然的认为按顺序计算下一个数比较耗时。