时间戳

首页 > 解决方案 > 查找未出现在数组中的最小正整数

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

问题描述

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

我本质上是在寻找蛮力选项，因为我不知道算法/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
            }  
    }
}

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

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

谢谢你的帮助！

标签： javascriptarraysfor-loop

解决方案

您可以使用以下方法执行此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

推荐阅读