javascript - 如何以较少的时间复杂度编写代码以找到给定数组范围内的缺失元素？

我的函数应该在给定的数组范围内返回缺少的元素。
因此，我首先对数组进行排序，并检查i和i + 1之间的差是否不等于1，我返回了缺少的元素。

// Given an array A such that:
// A[0] = 2
// A[1] = 3
// A[2] = 1
// A[3] = 5
// the function should return 4, as it is the missing element.

function solution(A) {
  A.sort((a,b) => {
    return b<a;
  })
  var len = A.length;
  var missing;
  for( var i = 0; i< len; i++){
    if( A[i+1] - A[i] >1){
      missing = A[i]+1;
    }
  }
  return missing;
}

我确实喜欢上面的内容，但是如何更有效地编写呢？

最佳答案

您可以将每个值放入sort中，找到最小值，然后从最小值开始进行迭代，而不是Set来检查集合中是否有相关数字O(N)。 (集合保证了O(1)查找时间)

const input1 = [2, 3, 1, 5];
const input2 = [2, 3, 1, 5, 4, 6, 7, 9, 10];
const input3 = [3, 4, 5, 6, 8];

function findMissing(arr) {
  const min = Math.min(...arr);
  const set = new Set(arr);
  return Array.from(
    { length: set.size },
    (_, i) => i + min
  ).find(numToFind => !set.has(numToFind));
}
console.log(findMissing(input1));
console.log(findMissing(input2));
console.log(findMissing(input3));

关于javascript - 如何以较少的时间复杂度编写代码以找到给定数组范围内的缺失元素？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50942303/