给定整数数组，则返回其中不存在的最小正整数

function solution(A);

function solution(A) {
  for (i = 1; i < 1000000; i++) {
    if(!A.includes(i)) return i;
  }
}

#1 楼

那是一个很好的简单解决方案，有两个问题：当A包含[1..1000000]或[1..999999]范围内的所有值时，它将给出错误的结果，分别返回undefined而不是1000001和1000000。
不满足时间复杂度要求，而是\ $ O（n ^ 2）\ $而不是\ $ O（n）\ $。

第一个问题很容易解决通过调整循环的结束条件来解决问题。

第二个问题比较棘手，是练习中有趣的部分。
考虑此算法，即\ $ O（n）\ $时间和\ $ O（1）\ $在空间中：


从头开始遍历A的元素，并且对于每个值A[i]，如果A[i] - 1是数组中的有效索引，然后重复交换A[i]和A[A[i] - 1]，直到A[i]在正确的位置（等于i + 1的值），或者A[i]和A[A[i] - 1]相等。


这应该将值排序到正确的位置，例如那A[i] == i + 1，当po ssible


再次遍历元素以查找其中A[i] != i + 1的索引（如果存在），则缺失值为i + 1

如果到达循环的末尾而没有返回值，则缺少的值为A.length + 1。

这是在JavaScript中实现此值的一种方法：

var firstMissingPositive = function(nums) {
    var swap = function(i, j) {
        var tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    };

    for (let i = 0; i < nums.length; i++) {
        while (0 < nums[i] && nums[i] - 1 < nums.length
                && nums[i] != i + 1
                && nums[i] != nums[nums[i] - 1]) {
            swap(i, nums[i] - 1);
        }
    }

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return nums.length + 1;
};

注意：进行验证或其他实现方式，
您可以在leetcode上提交。

#2 楼

这个解决方案怎么样？如果我没记错的话，该解决方案应该满足所有要求：


创建第二个数组
遍历输入数组的所有元素
对于每个数字，将第二个数组中的各个键设置为true
遍历第二个数组并返回第一个键，该键的值返回为undefined

如果找不到匹配项，则返回1 ，因此它也适用于空的输入数组

function findNumber(values) {
  let result = [];

  for (let i = 0; i < values.length; ++i) {
    if (0 <= values[i]) {
      result[values[i]] = true;
    }
  }

  for (let i = 1; i <= result.length; ++i) {
    if (undefined === result[i]) {
      return i;
    }
  }

  return 1
}

自己尝试一下


Patrick和我讨论了我们解决方案的实时性能（这是Patrick使用Set的优雅解决方案）。我们建立了一个测试，在输入数组中包含大约1000个元素，其中包括许多负值。您可以自己尝试测试。


JollyJoker在注释中使用JavaScript的内置filter，reduce和findIndex建议了类似版本。我修复了针对极端情况的建议解决方案，并将其添加到性能测试中。现在，您可以测试所有三种解决方案。请记住，这些内置函数会带来一些开销。


Janos现在也为其算法添加了代码。为了完成性能测试，我还添加了它，这是包含所有四个解决方案的最后的小提琴。

#3 楼

为了满足O（N）时间复杂度，请构造O（N）时间和空间复杂度为Set()，然后使用while循环，该循环也被视为相对于NO（N）为恒定时间（谢谢，wchargin） ，因为最大可能的迭代次数等于N并且Set#has()运算的平均性能为O（1）。因为O（N + N）= O（N），关于时间复杂度，所以此解决方案是时间和空间上的整体O（N）性能：

function solution(A) {
  const set = new Set(A);
  let i = 1;

  while (set.has(i)) {
    i++;
  }

  return i;
}

尽管这是一个相对简单且看似优雅的实现，但是当使用数组作为非负整数的理想哈希表时，insertusernamehere的解决方案无疑要快一个数量级。

#4 楼

function solution(A) {
  for (i = 1; i < 1000000; i++) {
    if(!A.includes(i)) return i;
  }
}

与您的间距保持一致。您可以在for之后使用空格，但不要为if使用空格。该空格有助于将语言构造与函数调用分开。

对于使用花括号的语言，请始终将单行放在括号中（明确地建立循环边界），并希望将它们放在单独的行上以提高可读性，维护性。 ，然后调试（断点！）。

如果len(A) >= 1,000,000会发生什么？使用数组的长度而不是任意值。参见下文。


您可以通过对数组中的任何非正值进行过滤/分区来简化此问题。拥有正整数的已过滤数组之后，就可以使用已过滤的长度来确定最低正整数的上限。对于不同的整数序列\ $ D = [1,2,3，...，n] \ $，最低的正整数保证为\ $ n + 1 \ $。如果从\ $ D \ $中删除任何值并将其替换为其他任何值（或简单地将其删除），则\ $ D \ $的最低正整数在\ $ [1，n] \ $范围内。要找到它，我们可以简单地在布尔表中跟踪整数，直到\ $ n \ $标记见证的整数。对布尔数组的线性搜索以查找第一个未标记的条目，将为我们提供丢失的最低正整数的从零开始的索引。添加一个，使其再次基于基础。筛选，标记见证人和搜索都是线性操作。

注意-由于您知道上限，因此可以通过第二次过滤器通过来删除范围大于数组长度的任何元素，从而进一步缩小范围。如果您在较小的数组中加载了较大的值，则对数据局部性有帮助。

尽管使用布尔数组确实可以满足您的空间复杂性要求，但确实存在恒定的空间解决方案。请记住，过滤后的数组中的每个元素都是正数，因此我们可以将每个值的正负号重新用作观察序列值的信号。我们可以像上面的布尔数组一样使用过滤后的数组的索引。我们将搜索仍然为正的第一个值，而不是搜索标记为false（目击者）的第一个元素。

solution(A)
    Filter non-positive values from A
    Filter values larger than min(N-1, 999999) from A
    For each int in A that wasn't filtered out
        Let a zero-based index be the absolute value of the int - 1
    For each index upto min(N-1, 999999)
        if A[index] is positive, return the index + 1 (to one-based)
    otherwise return min(N, 100000)

所以数组\ $ A = [1 、、 2、3、5、6] \ $进行以下转换：

abs(A[0]) = 1, to_0idx = 0, A[0] = 1, make_negative(A[0]), A = [-1,  2,  3,  5,  6]
abs(A[1]) = 2, to_0idx = 1, A[1] = 2, make_negative(A[1]), A = [-1, -2,  3,  5,  6]
abs(A[2]) = 3, to_0idx = 2, A[2] = 3, make_negative(A[2]), A = [-1, -2, -3,  5,  6]
abs(A[3]) = 5, to_0idx = 4, A[4] = 6, make_negative(A[4]), A = [-1, -2, -3,  5, -6]

线性搜索第一个正值将返回索引3。返回到基于1的索引将导致\ $ solution（A）= 3 +1 = 4 \ $

#5 楼

需要注意的一件事是允许使用多少空间。您最多可以使用O(n)空间（足以制作数据的完整副本）。您的代码当前很慢，因为它使用O(n) q 4312079q语句，每个语句都是in。这意味着，如果仅存在O(n)语句为in的数据结构，则可以解决您的问题。值得庆幸的是，O(1)恰好具有此属性。因此，您需要对解决方案进行的唯一更改就是将Set变成list。

#6 楼

在JavaScript中，您可以执行以下操作：



首先，使用JavaScript Array.sort()方法对数组进行排序，复杂度为\ $ O（n \ log（n））\ $（在这里说明）：

var A=[4,3,2,1,0,-3];
A.sort(function(a, b){return a-b});
//returns the array ordered [-3,0,1,2,3,4]

仅迭代有序数组。对于每个值，请检查该值是否大于0，并且数组上的下一个元素是否不等于当前值+1。

function(A){
    for(var i=0;i<A.length-1;i++){// iterate until  penultimate element
        if(A[i]>0 && A[i+1]!=(A[i]+1)){
            return (A[i]+1);
        }
    }
}

#7 楼

通过简单地首先对数组进行排序，剥离所有非正整数并从那里开始搜索，您可以找到比已经给出的解决方案更快的解决方案-这使算法成为\ $ O（n \ log n ）\ $算法，在最坏的情况下，最好的情况是\ $ O（n）\ $算法，不需要任何额外的空间。

将所有正数加到设置并找到不在该集合中的最小正数。如果要在少于\ $ O（n \ log n）\ $的时间内完成此操作，则需要使用位向量；当要检查的元素等于n时，遍历所有元素并将向量中的位true设置为n。这将花费\ $ O（n）\ $时间和\ $ O（n）\ $空间。

要获取位向量的大小，只需找到最大的整数（而在您搜索时最小） ）并分配那么多位。这也可以在\ $ O（n）\ $时间内完成。如果最小整数不是1，则您要查找的数字是1。

#8 楼

使用set会导致问题O（N lg N），因为每个插入，删除和查找的关联目录都是lgN。除非您使用关联目录的哈希版本，否则在O（1）中找不到下一个，因为最差的情况是O（N）。

使用比较函数进行排序始终会导致O（N lg N），但是没有其他专门的排序，例如计数排序。

所以我们可以尝试对计数排序进行专门化，因为我们对如何计算不感兴趣，所以称其为存在排序

我们进一步将原始数组中的数字范围修剪为仅包括1到100000之间的数字。

此方法的伪代码：

min = 1
max = 100000

bool num[100000] = false // 100000 long array of bool, add 1 (one) if your language array index start at 0 (zero)


for (i = 1; i < 1000000; i++) {
  can = A[i];
  if(can >= min && can <= max) {
    num[can] = true;    // register numbers that exist in our range
  }
}

for (i = min; i <= max; i++)
  if (!num[i])
    return i;

#9 楼

这是一个PHP解决方案（初始测试）：

<?php
$a = array(
    2, 1, 3, 5, 6, 7,
);

function solution(array $a = array()){
    /**
     * Assumes that the first positive integer
     * in an empty array will be 1 - also stops
     * potential for infinite loop in while()
     * below
     */
    if(!count($a)){
        return 1;
    }

    $i = 0;

    while(in_array(++$i, $a)){}

    return $i;
}

echo solution($a);

，这是基于以下注释中反馈的重构版本：

function solution(array $a = array()){
    /**
     * Assumes that the first positive integer
     * in an empty array will be 1 - also stops
     * potential for infinite loop in while()
     * below
     */
    if(!count($a)){
        return 1;
    }

    /**
     * Lowest possible number in set
     * -1 so it starts counting at
     * -1000000
     */
    $i =-1000001;
    $c = 1;

    while($c){
        $i++;
        if(($i > 0 && !in_array($i, $a)) || $i > 1000000){
            $c = 0;
        }
    }

    /**
     * If $i is negative, the lowest positive
     * integer in set will be 1, otherwise it
     * will be the set value of $i unless $i
     * is out of range for this task
     */
    if($i <= 1000000){
        return ($i < 1) ? 1 : $i;
    }
    return 'Value out of range';
}

#10 楼

Java中的以下解决方案应在时间和空间复杂度的范围内：

public int solution(int[] A)
{
    java.util.HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(A.length); //O(n) space
    for (int i : A) // O(N)
    {
        if (!map.containsKey(i))
        {
            map.put(i, i);
        }
    }
    int smallestPositive = 1;
    for (int i = 1; i < 1000001; i++) // ~O(N)
    {
        if (map.containsKey(i) && map.get(i) <= smallestPositive)
        {
            smallestPositive = map.get(i) + 1;
        }
    }
    return smallestPositive;
}

我要写的是，您甚至可以抛弃HashMap并循环遍历A第二个循环为1,000,000，这是一个常量，应该可以忽略不计，但是看起来他们特别指出了一个问题：\ $ N \ $是100,000，这是较小的，因此您可以认为第二个循环是\ $ O（ n）\ $时间。

它总计为\ $ O（n）+ O（n）= O（n）\ $时间和\ $ O（n）\ $空间。