11

我试图弄清楚如何找到这样的数字序列中的第一个缺失数字(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;
    }
}

首先,它在数字序列中的“洞”之后给了我第一个数字,其次,如果我不插入中断,它会继续提醒所有在“洞”之后出现的数字。我只想要从 1 到 32 的数字序列的第一个缺失数字。我该怎么做?

希望提前帮助和感谢;-)

4

11 回答 11

14

这个怎么样

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;
   }
}
于 2013-09-17T15:17:21.000 回答
14

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
于 2016-10-16T05:35:05.137 回答
3

By if(mynumbers[i] - mynumbers[i-1] != 1),您的意思是说该系列将始终递增1

var missing = (function (arr) {
    var i;
    for (i = 0; i < arr.length; ++i) {
        if (i + arr[0] !== arr[i]) return i + arr[0];
    }
    if (i < 32)            // if none missing inside array and not yet 32nd
        return i + arr[0]; // return next
}([1,2,3,6,9,10])); // 4
alert(missing);
于 2013-09-17T15:07:15.560 回答
2

无论如何,你都需要休息。这就是它的用途;阻止循环继续到最后。并且您应该使用数组的长度而不是硬编码 32 作为结束条件,因为您的数字最多只能达到 32,但列表中可能存在漏洞,因此数组中不会有 32 个元素。

既然你知道每个元素应该比前一个元素多1,那么洞里的数字就很明显了mynumbers[i - 1] + 1

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

编辑:这仅适用于缺失的数字不是 1。要抓住它,您需要检查if (mynumbers[0] != 1)

于 2013-09-17T15:06:41.190 回答
1

编辑:

function findFirstMissing(array) {
    for (var i = 0; i < array.length; i++) {
        if (i+1 !== array[i]) {
            return i+1;
        }
    }
}

function findFirstMissing(array) {
    for (var i = 0; i < array.length; i++) {
        if (array[i+1] - array[i] !== 1) {
            return array[i] + 1;
        }
    }
}

如果你这样做,那么将它存储在一个变量中很容易:

var missing = findFirstMissing(array);
于 2013-09-17T15:07:20.717 回答
1
const firstNonConsecutive = arr => arr.find((el, i, arr) => (arr[i] - arr[i-1]) !== 1 && i !== 0)

此解决方案适用于一组正数。

于 2017-12-25T00:18:55.327 回答
0

使用 array.reduce 查找第一个正缺失整数的解决方案。

function solution(A) {
  return [...A].sort().reduce((acc, curr, i, arr) => {
    if (acc > curr) {
      arr.splice(1);
      return acc;
    }
    else if (arr[i + 1] - curr > 1 || arr.length === i + 1) {
      arr.splice(1);
      return curr + 1;
    }
    return acc;
  }, 1);
}

这里有几个测试用例:

console.log('solution([1, 3, 6, 4, 1, 2])',  solution([1, 3, 6, 4, 1, 2]) === 5)
console.log('solution([1, 3, 2, 8, 4])', solution([1, 3, 2, 8, 4]) === 5)
console.log('solution([1])', solution([1]) === 2)
console.log('solution([-1])', solution([-1]) === 1)
console.log('solution([0])', solution([0]) === 1)
console.log('solution([-1, -4, -5, -6, -190343])', solution([-1, -4, -5, -6, -190343]) === 1)
于 2018-04-12T18:47:45.607 回答
0

有时,如果您知道它是一个小数组,您只需要简单:

let numbers = [1,2,3,6,9,10]
let m = 0

for (const i of numbers) if (i > ++m) break

console.log(m) // 4

如果从数组的开头删除 1 则有效:

numbers = [2,3,6,9,10]
m = 0

for (const i of numbers) if (i > ++m) break

console.log(m) // 1

如果数组可以是连续的,并且如果是这样你想要下一个最大的数字,那么:

numbers = [1,2,3,4,5,6,7,8,9]
m = 0

for (const i of numbers) if (i > ++m) break
if (m == Math.max(...numbers)) m++

console.log(m) // 10

又短又甜!

于 2019-07-31T07:22:01.077 回答
0
//Find the missing number in a series
//output must be 12 in a table of 3 given in below series
let abc = [3, 6, 9, 15, 18, 21, 24];
var def = [],
  ghi = [];
for (var i = 1; i <= abc.length; i++) {
  if (i !== abc.length) {
    var diff = abc[i] - abc[i - 1];
    if (def.includes(diff) === false) {
      def.push(diff);
    } else {
      ghi.push(diff);
    }
  }
}

var finalArr = [];
if (ghi.length > def.length) finalArr = ghi;
else finalArr = def;
var finaldiff = finalArr[0];
var finalVal = abc.find((e, i) => {
  if (e !== abc.length) {
    var diff = abc[i] - abc[i - 1];
    return diff > finaldiff;
  }
})

console.log(finalVal - diff);
于 2021-03-19T20:26:48.917 回答
-1
for(var i = 1; i < mynumbers.length; i++) {
    if(mynumbers[i] - mynumbers[i-1] != 1) {
        alert("First missing number id: "+mynumbers[i-1]+1);
        i = mynumbers.length; // Replace the break
    }
}

如果您愿意,可以添加初始检查:if (mynumbers[0] != 1) { ... }

于 2013-09-17T15:05:12.117 回答
-1

我认为这是两步解决方案的最简单和最佳形式。

对于这个问题,我认为没有比这个更好的解决方案了。

此代码使用最小编号。变量、循环、条件、内置函数和所有糟糕、草率、不必要的代码。

此代码可以处理任何长度的数组。

var mynumbers = new Array(76,77,78,79,80,81,82,83,84,125);

if(mynumbers.length > 1) {

  for(var i=0; i<=mynumbers.length-1; i++) {

    if(mynumbers[i+1] - 1 !== mynumbers[i]) { 

      alert("First Missing Term is : "+parseInt(mynumbers[i]+1));
      break;
    }

  }

}
于 2019-07-31T08:11:24.943 回答