javascript - 编程,算法的问题
PHP中文网
PHP中文网 2017-06-12 09:25:56
0
4
969

前天面试了一个问题
请使用js,python,java,c,c++之类的语言,在10秒内计算出100亿的数据,并且(只能在3秒内)完成,偶数在奇数前
格式如下
1,2,3,4,5
输出结果是
2,1,4,3,6,5,
问题2:在1的代码之上,要求不能使用for while关键字,从100亿里面取所有的质数(时间不能超过3秒)
这个怎么搞?

PHP中文网
PHP中文网

认证高级PHP讲师

全部回复(4)
我想大声告诉你

第一个问题没看懂,是说2个数字为一对,然后偶数在奇数前面?

第二个问题简单啊,不能用循环,那就用数组迭代呗。

代言

话说 phpforeach 算么(笑

我觉得面试官的意图是让你写一个递归函数?嗯估计是。

Ty80

前天面试了一个问题
请使用js,python,java,c,c++之类的语言,在10秒内计算出100亿的数据,并且(只能在3秒内)完成,偶数在奇数前
格式如下
1,2,3,4,5
输出结果是
2,1,4,3,6,5,
问题2:在1的代码之上,要求不能使用for while关键字,从100亿里面取所有的质数(时间不能超过3秒)
这个怎么搞?


既然不能用 for while

那么递归性能不太够。。。但是我还是用了一些。。 For Performance

可能有很巧妙的办法

。。。 100亿 的体量 应该是有的。 我还没发现。

代码

100 亿有点大啊 我先 10 万了

var n = 1000 * 1000; 
var test = new Array(n).fill(n).map((e, idx) => idx); 

这样可以获得到 10 万长度的数组 自然数。


Next

  1. 偶数在前 奇数在后

观察之后发现,奇数 + 1偶数 - 1 就可以了

var isEven = n => n % 2 === 0; 

var res001 = test.map((e, idx) => {
    if (isEven(e)){
        return e - 1; 
    } else {
        return e + 1; 
    }
}); 

完成第一个问题

ScreenShot One

Next

下一个问题是在上面的基础上取得质数 即从 zs 里取得所有质数

查了一下关于质数的问题,别人说 质数分布在 6 的倍数的左边或者右边 那么我只要遍历 每一个6的倍数的左边和右边 并判断他们是不是质数即可。

链接: 判断一个数是否为质数/素数——从普通判断算法到高效判断算法思路

// 剔除第一个负数 
var zs = res001.slice(1); 

var is6x = n => n % 6 === 0; 


var isPrime = n => {
     let temp = Math.sqrt(n);  
     
     for(let i = 2; i <= temp; i++){
         if(n % i === 0){
             return false; 
         }
     }
     
     return true;  
}  


var lasts = zs.filter(is6x).reduce((acc, cur) => {
    let left = cur - 1, right = cur + 1; 
    if (isPrime(left)) acc.push(left); 
    if (isPrime(right)) acc.push(right); 
    
    return acc; 
}, []); 

console.log(lasts); 

ScreenShot Two

不知道对不对 ...

不过还需要把 小于 6 的质数 1 2 3 5 单独拼回去。 (这里没拼)

性能

把上面写的代码黏起来

var isEven = n => n % 2 === 0; 


var is6x = n => n % 6 === 0; 

var isPrime = n => {
     let temp = Math.sqrt(n);  
     
     for(let i = 2; i <= temp; i++)
        if(n %i== 0){
            return false; 
        }
     return true;  
}  


function timeTest(n){
    var test = new Array(n).fill(n).map((e, idx) => idx); 
    var res001 = test.map((e, idx) => {
        if (isEven(e)){
            return e - 1; 
        } else {
            return e + 1; 
        }
    }); 
    var zs = res001.slice(1); 
    
    var lasts = zs.filter(is6x).reduce((acc, cur) => {
        let left = cur - 1, right = cur + 1; 
        if (isPrime(left)) acc.push(left); 
        if (isPrime(right)) acc.push(right); 
        
        return acc; 
    }, []); 
    
    return lasts; 
}

test

var n = 1000 * 10000; 

console.time('1000 万')
timeTest(n); 
console.timeEnd('1000 万');

1000 万 结果如图


花了 13.8 秒 不可能做到 10 + 3 秒内完成 13.8 秒 不可能做到 10 + 3 秒内完成 100亿 的体量。

我的电脑是 i5-4210M 12G Chrome 58

JavaScript 做不到这样的性能: JavaScript 做不到这样的性能: 100亿 个数字 13 个数字 13 秒内 ....

好几个 G 的数据 ......

按照上面的思路来做,即使是 C/C++ 估计也很难13秒跑完100亿。

解决问题为主。

Links

判断一个数是否为质数/素数——从普通判断算法到高效判断算法思路

Ty80

首先感谢楼上的求质数的算法,我贴下我的结果和代码(只有1000万,一亿浏览器直接炸掉了,而且求质数那里不能用递归(我测试的结果),不然也得炸,只能迭代)。

浏览器里面的结果:

node里面的结果:

var arr = [];

console.time("1000万");
for( var i = 1; i <= 10000000; i++ ){
    arr.push(i);
}

for( var j = 0, len = arr.length;j < len; j+=2 ){
    arr[j]++;
    arr[j+1]--;
}

function isPrime(num,sqrt){
     if(num == 1)
     return false;
     if(num == 2 || num == 3 )  
     return true;  
     if(num % 6 != 1 && num % 6 != 5)  
     return false;  
     var tmp = sqrt(num);  
     for(var i= 5;i<=tmp; i+=6 )  
        if(num % i == 0 || num % ( i + 2) == 0 )  
        return false ;  

     return true;  
};

function getPrime(sourceArray,array,isPrime,sqrt){

    sourceArray.map(function(num,idx){
        if(isPrime(num,sqrt)){
            array.push(num);
        }
    });

    return array;
};

var result = getPrime(arr,[],isPrime,Math.sqrt);

console.timeEnd("1000万");
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板