数组中不存在的最小整数

Question

编写一个函数:

函数解($ 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]范围内的整数。复杂性：

预期最坏情况时间复杂度为O（N）；预期最坏情况空间复杂度为O（N），超出输入存储（不包括输入参数所需的存储）。可以修改输入数组的元素。

我的尝试:

function solution($A) {
    $b=min($A);
    $c=max($A);
     for($i=$b; $i<=$c;$i++){
         if($b>0){
                if($b!=1){
                    return 1;
                    }else{
                        for($x=1;$x<=$c;$x++){
                            $b=1;
                            $b=$b+$x;
                            if(!in_array($b,$A)){
                                return $b;
                                }
                        }
                    }
         }else if($b<0 && $c<0){
             return 1;
             }else if($b<0 && $c>0){
                 //was working on this case..
                 }
        //echo $test.'<br>';
    }
}

根据结果，此尝试的正确率为40%。

Answer 1

提示没有说数组是有序的，所以不能只是递增。您也不希望重复进行线性搜索，因为数组可能很大。存储在类似散列集的东西中(用于快速查找)，并跳过负数:

PHP实现：

<?php
  function solution(array $arr) {
    $set = [];

    foreach ($arr as $value) {
      if ($value > 0) {
        $set[$value] = $value;
      }
    }

    for ($i = 1; isset($set[$i]); $i++);

    return $i;
  }


  echo solution(array(1, 3, 6, 4, 1, 2));//5
  echo solution(array(1, 2, 3));//4
  echo solution(array(-1, -2));//1
?>

Answer 2

function solution($A) {
  $a = array_flip($A);
  for($i=1; isset($a[$i]);$i++);
  return $i;
}

解决方案的性能得分为100%！！

Answer 3

不确定你想在代码中做什么，但是从1开始，检查并递增。只要在数组中找不到< code>$i，循环就会停止:

function solution($A) {
    for($i=1; in_array($i, $A); $i++);
    return $i;
}