当前位置:Gxlcms > JavaScript > JavaScript趣题:出Bug的等差数列

JavaScript趣题:出Bug的等差数列

时间:2021-07-01 10:21:17 帮助过:42人阅读

一个程序在创建等差数列时出了Bug,等差数列中某一项被丢失了,其他项好完好,请找出这个丢失项。

比如:1,3,5,9,11,这里的丢失项很明显是7

你得写一个函数,findMissing (list) ,它接收一个等差数列列表,列表至少有3个元素,丢失项不会是第一个或最后一个。

来个例子:


findMissing ([1,3,5,9,11]); // 7

PS:这是Facebook在interviewstreet上的工程师挑战例题,大家拿张白纸和笔,写写划划应该很快能解出来。

好了,咋们来看看解题思路:

我个人感觉,对付此类问题,也就是说,至少3个元素的题目,它往往暗示了你,三个元素内要“决出胜负”。

对于这个题目,三个元素内要推算出等差数列的公差。

先来看前三个元素的例子:

7,5,1

大家一眼就可以看出,第一个元素和第二个元素相差-2,第二个元素和第三个元素相差-4,那么公差是-2

所以,对于递减数列这种情况,公差是:


Math.max(list[1]-list[0],list[2]-list[1]);

再看另一个倒过来的例子:

1,5,7

第一个元素和第二个元素相差4,第二个元素和第三个元素相差2,那么公差是2

对于递增数列的情况,公差就是:


Math.min(list[1]-list[0],list[2]-list[1]);

既然算出来了公差,那剩下的事儿就好办了,从第一个数依次用公差,一一比对列表中的数,遇到不相等的,那就是Miss的项了。

var findMissing = function (list) {
    var diff1$0 = list[1]-list[0];
    var diff2$1 = list[2]-list[1];
    var diff = diff1$0 < 0 ? Math.max(diff1$0,diff2$1) : Math.min(diff1$0,diff2$1);
    for(var i=list[0],j=0;j<=list.length;i+=diff,j++){
        if(i !== list[j]){
            return i;
        }
    }
}

以上就是JavaScript趣题:出Bug的等差数列 的内容,更多相关内容请关注PHP中文网(www.gxlcms.com)!

人气教程排行