在一系列数字中找到第一个缺失的数字

Question

我试图弄清楚如何找到像这样的数字序列的第一个缺失数字(1,2,3,5,6,9,10,15)

我想把第一个缺失的数字#4放入变量供以后使用,但不知道怎么做？

我试过这个,但这只给了我最后一个数字:

var mynumbers=new Array(1,2,3,6,9,10);
for(var i = 1; i < 32; i++) {
    if(mynumbers[i] - mynumbers[i-1] != 1) {
        alert("First missing number id: "+mynumbers[i]);
        break;
    }
}

首先,它给出了我在numberequence中的"洞"之后的第一个数字,其次,如果我没有插入一个中断,它会继续警告所有在"洞"之后出现的数字.我只想要从1到32的第一个缺失数字序列.我该怎么办？

希望得到帮助并提前感谢;-)

Answer 1

O(n)解决方案很简单 ,但这是一个常见的面试问题,我们经常寻找O(log n)时间解决方案.这是javascript代码.它基本上是一个修改过的二进制搜索.

function misingNumInSeq(source, min = 0, max = source.length - 1){
    if(min >= max){
        return min + 1;
    }
    let pivot = Math.floor((min + max)/2);
    // problem is in right side. Only look at right sub array
    if(source[pivot] === pivot + 1){
        return misingNumInSeq(source, pivot + 1, max);
    } else {
        return misingNumInSeq(source, min , pivot);
    }
} 

产量

misingNumInSeq([1,2,3,5,6,9,10,15])
4

Answer 2

这个怎么样

var mynumbers = new Array(1,2,3,6,9,10);
var missing;

for(var i=1;i<=32;i++)
{    
   if(mynumbers[i-1] != i){
        missing = i;
        alert(missing);
        break;
   }
}