求数组中不出现的最小正整数

Question

我正在尝试以下练习来提高我的在线技能，我遇到了以下问题。

这是一个演示任务。

编写一个函数：class Solution{public int Solutions（int[]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）。

<?php

class Solution {
    public function($A) {
        $posInts = [1, 2, 3, 4, 5, 6, 7, 8, 9];
        $diffs = array_diff($postInts, $A);
        $smallestPosInt = min($diffs);
        return $smallestPosInt;
    }
}

现在我很不确定我在这里做错了什么，或者我如何用更好的算法重写代码。

Answer 1

查看这个答案，使用Javascript以一种具有最佳性能的方式工作-如果我没有弄错-O（N）。

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

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

Answer 2

如果允许我们修改输入，请就地执行此操作，否则创建一个大小为n 1的新数组：

对于原始数组中遇到的每个元素，如果它大于n 1或小于1，则在元素的索引处分配0（如果就地执行，则索引为-1）；否则，在数组的索引处为值赋值1，如果不同，则在其自己的索引处赋值0。然后运行第二次遍历，并报告第一个大于零的索引（如果就地执行，则为索引1），值为0或n1。

[1, 3, 6, 4, 1, 2]

=>

[1, 1, 1, 1, 0, 1]

report 5

Answer 3

我只会循环（递增）任何可能的整数：

function solution($A) {
    $result = 1;
    $maxNumber = max($A);
    for (; $result <= $maxNumber; $result++) {
        if (!in_array($result, $A)) {
            break;
        }
    }
    return $result;
}

var_dump(solution([1, 3, 6, 4, 1, 2])); // int(5)
var_dump(solution([1, 2, 3])); // int(4)
var_dump(solution([-1, -3])); // int(1)

// As a bonus, this also works for larger numbers:
var_dump(solution([1, 3, 6, 4, 1, 2, 7, 8, 9, 10, 11, 12, 13, 5, 15])); // int(14)

关于性能的编辑：

正如评论中指出的那样（你自己已经说过了），这不是一个非常有效的解决方案。

虽然我目前没有足够的时间进行真正的性能测试，但我认为这应该接近O(n)解决方案:(记住，我不确定数组是如何在PHP的C端实现的)

function solution($A) {
    $result = 1;
    $maxNumber = max($A);
    $values = array_flip($A);
    for (; $result <= $maxNumber; $result++) {
        if (!isset($values[$result])) {
            break;
        }
    }
    return $result;
}
// Not posting the output again because it is naturally the same ;) 

这里的“技巧”是首先翻转数组，使值成为索引。因为a)我们不关心原始索引，b)我们不关心重复值是否会相互覆盖，所以我们可以安全地这样做。

使用isset（）代替in_array（）应该要快得多，因为它基本上只检查变量（在本例中存储在数组的特定索引中）是否存在，因此PHP不必迭代数组来检查我们循环的每个数字是否存在于其中。

P.S.：经过三思，我认为这可能仍然更接近O（n*2），因为max（）可能会循环找到最大值。您也可以删除该行，只需检查PHP中作为紧急出口的最高数字，如下所示： 对于（; $result