Home >Web Front-end >JS Tutorial >Interesting JavaScript question: Buggy arithmetic sequence
一个程序在创建等差数列时出了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)!