查找未出现在数组中的最小正整数

Question

我正在尝试解决 leetcode 类型问题，这是一个练习问题，伴随着我需要为工作做的即将进行的代码测试，但我遇到了麻烦。谁能帮助我了解出了什么问题？

\n

我本质上是在寻找暴力选项，因为我不知道 algos/DS。

\n

                                                       PROBLEM:\n

\n

写一个函数：

\n

函数解(A);

\n

给定一个包含 N 个整数的数组 A，返回 A 中未出现的最小正整数（大于 0）。

\n

例如，给定 A = [1, 3, 6, 4, 1, 2]，该函数应返回 5。

\n

给定 A = [1, 2, 3]，该函数应返回 4。

\n

给定 A = [\xe2\x88\x921, \xe2\x88\x923]，该函数应返回 1。

\n

为以下假设编写一个有效的算法：

\n

N 是 [1..100,000] 范围内的整数；\n数组 A 的每个元素都是 [\xe2\x88\x921,000,000..1,000,000] 范围内的整数。

\n

                            HERE IS MY SOLUTION: \n\nfunction solution(A) {\n    let newArray = A.sort(function(a, b){return a-b})\n        let lowestNumber = 1\n        for(i=0; i < newArray.length; i++) {\n            if(lowestNumber > newArray[0]) {\n                return lowestNumber\n            }\n            if(lowestNumber == newArray[i]) {\n                lowestNumber = lowestNumber + 1\n            }\n            if(i = newArray.length - 1) {\n                return lowestNumber\n            }  \n    }\n}\n

\n

下面的代码片段没有像我期望的那样工作。我相信，lowestNumber 没有增加，而且循环也在这里退出。

\n

if(lowestNumber == newArray[i]) {\n                lowestNumber = lowestNumber + 1\n

\n

感谢您的帮助！

\n

Answer 1

您可以O(N)使用以下方法来做到这一点Map()：

• 首先设置数组中的每个数字。
• 然后从 1 开始查找并返回序列中缺失的数字。

function solution(arr) {
  const seen = new Map();

  for (let i = 0; i < arr.length; i++) {
    seen.set(arr[i]);
  }

  for (let i = 1; i <= arr.length + 1; i++) {
    if (!seen.has(i)) return i;
  }

  return 1;
}

console.log(solution([1, 3, 6, 4, 1, 2])); //-> 5
console.log(solution([1, 2, 3]));          //-> 4
console.log(solution([-1, -3]));           //-> 1