查找数组中没有出现的最小正整数

Question

我正在尝试解决一个leetcode类型问题，这是一个实践问题，它伴随着即将到来的代码测试，我需要为工作做一个，我遇到了麻烦。任何人都可以帮助我了解出了什么问题？

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

                                                       PROBLEM:

编写一个函数:

功能溶液（A）；

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

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

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

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

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

n是范围[1]内的整数..100,000];数组A的每个元素都是一个整数，范围在-1，000，000之间..1,000,000].

                            HERE IS MY SOLUTION: 

function solution(A) {
    let newArray = A.sort(function(a, b){return a-b})
        let lowestNumber = 1
        for(i=0; i < newArray.length; i++) {
            if(lowestNumber > newArray[0]) {
                return lowestNumber
            }
            if(lowestNumber == newArray[i]) {
                lowestNumber = lowestNumber + 1
            }
            if(i = newArray.length - 1) {
                return lowestNumber
            }  
    }
}

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

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

谢谢你的帮助！

Answer 1

最快的解决方案

function solution(A) {
  // write your code in JavaScript (Node.js 8.9.4)
  if (!A) return 1;
  A.sort();
  if (A[A.length - 1] < 1) return 1;
  const setA = new Set(A);
  let length = setA.size;
  for (let i = 1; i <= length; i++) {
    if (!setA.has(i)) {
      return i;
    }
  }

  return length + 1;
}

Answer 2

您可以使用Map（）在O（N）中执行此操作：

• 首先设置数组中的每个数字
• 然后从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

Answer 3

我想你的<代码>

和最低数量

你的努力看起来漫不经心，所以你必须在面试中提高自己的水平。

const integers = [5, -345, 562456, 95345, 4, 232, 1, 2, 3, 7, -457];

function solution(A) {
  let newArray = A.sort((a, b) => a - b);
  let lowestNumber = 1;
  for (let i = 0; i < newArray.length; i++) {
    const n = newArray[i];
    if (n > 0) {
      if (lowestNumber < n) {
        return lowestNumber;
      } else {
        lowestNumber = n + 1;
      }
    }
  }
  return lowestNumber;
}

console.log(solution(integers));