微软面试题之64

既然是算法题，就不要把问题想得太简单。
1、能不能一秒钟之内算出答案？
2、数字范围扩大到64位整数，第10000个数是多少？

我暂时先不说我的算法，先给出我的计算结果
99:1500
100:1536
101:1600
999:51018336
1000:51200000
1001:51840000
1499:854296875
1500:859963392
1501:860934420
4999:50779978334208
5000:50837316566580
5001:50960793600000
9999:288230376151711744
10000:288325195312500000
10001:288555831593533440

我用matlab实现的算法，搜索是用2分法的与C相比matlab是慢一点 但是也均在1s以内搞定

99: 1500       0.011233
100: 1536       0.005691
101: 1600       0.005574
999: 51018336       0.064719
1000: 51200000       0.06136
1001: 51840000       0.060935
1499: 854296875       0.093533
1500: 859963392       0.093454
1501: 860934420       0.095523
4999: 50779978334208       0.37203
5000: 50837316566580       0.35856
5001: 50960793600000       0.36
9999: 257363915118311232       0.9204
10000: 257492065429687488       0.92843
10001: 257492065429687520       0.9109

不过最后到9999后面的几个不对  不知道是否是因为数据类型的问题
但是matlab的默认数据类型就是double 64位的 我相信我的结果   

不知道其他人的结果是如何。

matlab作了下优化  这个是新的结果 主要是时间再快点了

99: 1500       0.009685
100: 1536       0.005243
101: 1600       0.005221
999: 51018336       0.057426
1000: 51200000       0.057376
1001: 51840000       0.057008
1499: 854296875       0.087089
1500: 859963392       0.086993
1501: 860934420       0.086771
4999: 50779978334208       0.30262
5000: 50837316566580       0.3103
5001: 50960793600000       0.31363
9999: 257363915118311232       0.66192
10000: 257492065429687488       0.62489
10001: 257492065429687520       0.64989

楼主的三种算法时间复杂度是多少？
第一个应该是 O(n)吧；
第二个也是O(n)吧；
那第三种呢？应该也是O（n）吧；

遍历是哪种遍历 不会是 野蛮的用自然数烈去试吧。。
遍历到1000左右 还是可以很快的出来的  跟我的算法的结果是一致的
1500 太恐怖了  我没能遍历下去
还有 你遍历到的1500的结果 跟我的不一样 。。。

微软找搞java的之后，问之:嗯，java能搞的这么出色，不错，有学。net的潜质。我看好你。

#!/usr/bin/python3

def getMaxN(uglies,count,n):
    ma=count-1
    mi=0
    while mi<ma:
        i=(ma+mi)//2
        maxN=uglies[i]*n
        if maxN>uglies[count-1]:
            ma=i
        else:
            mi=i+1
    i=(ma+mi)//2
    return uglies[i]*n

def getUglyDigit(number):
    uglies=list(range(1,number+1,1))
    for i in range(1,number,1):
        m2=getMaxN(uglies,i,2)
        m3=getMaxN(uglies,i,3)
        m5=getMaxN(uglies,i,5)
        uglies[i]=min(m2,m3,m5)
    return uglies[number-1]

print(getUglyDigit(1500))

油菜

只是算法题，和语言有个啥关系！

我的算法跟前面几位的不太一样，不是从第一个开始按顺序计算丑数序列的，而是先基于因数分解计算任意V以内有多少个丑数，然后用二分法查找第N个丑数。
“matlab的默认数据类型就是double 64位”，用浮点数计算的结果能保证精确吗？
当然我的算法可能有问题，计算结果也可能不正确。

public class Q64
{
    //基于因数分解求出val以内有多少个丑数（不包含1)
    static int nums235(long val)
    {
        int n = 0;
        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;
            }
        }
    }
    static long check(long val)
    {
        long v = val;
        while(v%2==0) v/=2;
        while(v%3==0) v/=3;
        while(v%5==0) v/=5;
        if(v!=1)
            System.out.println(val + " 不是丑数");
        return val;
    }

    static void calc(int n)
    {
        long val = numOfIndex(n);
        System.out.println(n +  ":" + val);
        check(val);
    }
    static void calc1(int n)
    {
        calc(n-1);
        calc(n);
        calc(n+1);
    }
    public static void main(String[] args)
    {
        long t = System.currentTimeMillis();
        calc1(100);
        calc1(1000);
        calc1(1500);
        calc1(5000);
        calc1(9918);
        calc1(10000);
        System.out.println("used time " + (System.currentTimeMillis()-t) + " ms.");
        /*
        check(257363915118311232L); 
        check(257492065429687488L); 
        check(257492065429687520L);*/ 

    }

}

输出结果：
99:1500
100:1536
101:1600
999:51018336
1000:51200000
1001:51840000
1499:854296875
1500:859963392
1501:860934420
4999:50779978334208
5000:50837316566580
5001:50960793600000
9917:256783692909772800
9918:257073640316928000
9919:257363915118311250
9999:288230376151711744
10000:288325195312500000
10001:288555831593533440
used time 234 ms.