如何编写具有较少时间复杂度的代码来查找给定数组范围内的缺失元素？

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]));

Answer 2

好了，从问题（应该返回一个数字）和所有现有解决方案（至少是示例）来看，列表看起来是唯一的。对于这种情况，我认为我们可以sum整个数组，然后用这些数字之间的期望总和减去即可生成输出。

N个自然数的总和

1 + 2 + ....... + i + ... + n 我们可以通过 n * (n+1) / 2

现在假设，在我们的数组中，min是i，max是n

所以i + (i+1) + ..... + n我们可以评估

A = 1 + 2 + ..... + (i-1) + i + (i+1) + .... n（即n*(n+1)/2）

B = 1 + 2 + ..... + (i-1) 和

C = A - B将给我们（i +（i + 1）+ ... + n）的总和

现在，我们可以对数组进行一次迭代，并评估实际的总和（假设D），C - D并将给出缺失的数字。

首先让我们在每个步骤中都创建相同的内容（对于性能而言并非最佳，但更具可读性），然后我们将尝试在单个迭代中进行操作

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

let sumNatural = n => n * (n + 1) / 2;

function findMissing(array) {
  let min = Math.min(...array),
      max = Math.max(...array),
      sum = array.reduce((a,b) => a+b),
      expectedSum = sumNatural(max) - sumNatural(min - 1);
      return expectedSum - sum;
}

console.log('Missing in Input1: ', findMissing(input1));
console.log('Missing in Input2: ', findMissing(input2));
console.log('Missing in Input3: ', findMissing(input3));

现在，让我们尝试做在一个单一的迭代（因为我们是去重复3次max，min和sum）

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

let sumNatural = n => n * (n + 1) / 2;

function findMissing(array) {
  let min = array[0],
      max = min,
      sum = min,
      expectedSum;
  // assuming the array length will be minimum 2
  // in order to have a missing number
  for(let idx = 1;idx < array.length; idx++) {
    let each = array[idx];
    min = Math.min(each, min); // or each < min ? each : min;
    max = Math.max(each, max); // or each > max ? each : max;
    sum+=each; 
  }

  expectedSum = sumNatural(max) - sumNatural(min - 1);
  return expectedSum - sum;
}

console.log('Missing in Input1: ', findMissing(input1));
console.log('Missing in Input2: ', findMissing(input2));
console.log('Missing in Input3: ', findMissing(input3));

Answer 3

sort您可以将每个值放入a Set,找到最小值,然后从最小值开始迭代,检查该集合是否具有相关数量,而不是ing 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));