如何有效地检查整数是否不在 Javascript 中的大数组中

Question

我正在做一项作业，我必须找到大于 0 且不在包含 100,000 个元素的巨大数组中的最小正整数。我能够做到，所以它是正确的，但显然我的解决方案花费的时间太长并且 returns 超时错误。

这是我目前的解决方案：

function solution(A) {
    let min=1

    while(A.includes(min) === true){
        min++
    }

    return min
}

是否有更快的方法来完成此操作而不涉及遍历每个元素？

编辑：哎呀伙计们，我忘记了这个问题的关键要素！

编辑 2：最小值为 -2，最大值为 100,000，并且它们不按顺序排列

Answer 1

对数组进行排序似乎是一个不错的起点。然后你可以从那里循环或二进制搜索找到你的最小正整数。

Answer 2

我相信这是一个测试，看看你是否知道未排序数组的搜索算法。你学过二分查找吗？

Answer 3

您可以获取一个对象并将每个想要的值添加到该对象。

然后取最小的键并检查它是否等于一并递增直到找不到键。否则return一个。

function getSmallest(array) {
    let temp = Object.create(null),
        smallest;

    for (const v of array) if (v > 0) temp[v] = true;
    smallest = +Object.keys(temp)[0];

    if (smallest !== 1) return 1;

    while (temp[++smallest]);

    return smallest;
}

console.log(getSmallest([2, 1, 0])); // 3
console.log(getSmallest([2, 3, 0])); // 1

Answer 4

我为以下语句编写了代码：“查找不在 -2 到 10000 之间的数字数组中的最小正整数”。

const arr = [5,4,6,7,5,6,4,5];
const p = new Array(10004);
arr.forEach(el => p[el + 2] = 1);
let answer = 10004;
for (let i = 3; i < 10004; ++i) {
  if (!p[i]) {
    answer = i - 2;
    console.log(answer);
    break;
  } else if (i == 10003) {
    console.log('no solution');
  }
}

如何有效地检查整数是否不在 Javascript 中的大数组中

How do I efficiently check if an integer is not in a massive array in Javascript

javascript

algorithm

performance

iterator

runtime-error