如何以较少的时间复杂度编写代码以在给定的数组范围内查找丢失的元素? [英] How to write the code with less time complexity for finding the missing element in given array range?

问题描述

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

My function should return the missing element in a given array range. So i first sorted the array and checked if the difference between i and i+1 is not equal to 1, i'm returning the missing element.

// 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;
}

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

I did like above, but how to write it more efficiently??

推荐答案

您可以将每个值放入 Set 中，而不是进行 sort 排序，找到最小值，然后然后从最小值开始进行迭代，检查集合中是否存在有问题的编号 O(N).(集合保证了 O(1)查找时间)

Instead of sorting, you could put each value into a Set, find the minimum, and then iterate starting from the minimum, checking if the set has the number in question, O(N). (Sets have guaranteed O(1) lookup time)

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

这篇关于如何以较少的时间复杂度编写代码以在给定的数组范围内查找丢失的元素?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！