JavaScript趣题：出Bug的等差数列

一个程序在创建等差数列时出了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.php.cn）！