javascript - 如何编写时间复杂度较低的代码来查找给定数组范围内丢失的元素？

Question

我的函数应该返回给定数组范围内缺失的元素。 所以我首先对数组进行排序并检查 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;
}

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

Answer 1

您可以通过使用一组缺失值来使用单循环方法。

在循环中，删除缺失集中的每个数字。

如果找到新的最小值，所有缺失的数字都会添加到缺失数字集中(最小值除外)以及新的最大值。

缺失数字集最后包含结果。

function getMissing(array) {
    var min = array[0],
        max = array[0],
        missing = new Set;
    
    array.forEach(v => {
        if (missing.delete(v)) return;                   // if value found for delete return
        if (v < min) while (v < --min) missing.add(min); // add missing min values
        if (v > max) while (v > ++max) missing.add(max); // add missing max values
    });
    return missing.values().next().value;                // take the first missing value
}

console.log(getMissing([2, 3, 1, 5]));
console.log(getMissing([2, 3, 1, 5, 4, 6, 7, 9, 10]));
console.log(getMissing([3, 4, 5, 6, 8]));