Codility练习题：查找数组中未出现的最小正整数 代码问题求优化

• 语法错误：首先你定义的公共方法缺少方法名，其次声明的数组变量为$posInts，调用时误写为$postInts，代码运行时会直接报错，这是得分低的首要原因。
• 逻辑缺陷：你硬编码了正整数范围仅为1_{9，当数组包含1}9全部元素时，array_diff返回空数组，调用min()会抛出错误，也无法得到正确结果10，完全无法覆盖所有测试用例。
• 效率不达标：即便你把预设正整数范围扩大到10万量级，array_diff的时间复杂度为O(n*m)，当n和m都达到10万级时，运算量会超过10^10，远超出时间限制要求。

首先明确核心逻辑：长度为N的数组，缺失的最小正整数一定在1~N+1范围内：如果数组包含1到N的所有正整数，就返回N+1，否则返回1到N中第一个缺失的数。
我们可以用原地哈希的方法实现O(n)时间复杂度、O(1)额外空间复杂度的算法：

1. 遍历数组，对于每个元素A[i]，如果它是1~N范围内的正整数，且没有放在对应下标A[i]-1的位置，就把它和A[A[i]-1]交换位置，直到当前位置的元素不符合交换条件为止。
2. 再次遍历数组，第一个满足A[i] != i+1的位置，i+1就是要找的最小缺失正整数。
3. 如果所有位置都满足A[i] == i+1，返回N+1即可。

<?php

class Solution {
    public function solution($A) {
        $n = count($A);
        for ($i = 0; $i < $n; $i++) {
            // 只处理1~n范围内的正整数，且未放在正确位置的元素
            while ($A[$i] > 0 && $A[$i] <= $n && $A[$A[$i] - 1] != $A[$i]) {
                $targetIndex = $A[$i] - 1;
                // 交换到正确位置
                $temp = $A[$targetIndex];
                $A[$targetIndex] = $A[$i];
                $A[$i] = $temp;
            }
        }
        // 找第一个缺失的正整数
        for ($i = 0; $i < $n; $i++) {
            if ($A[$i] != $i + 1) {
                return $i + 1;
            }
        }
        // 1~n都存在，返回n+1
        return $n + 1;
    }
}

内容的提问来源于stack exchange，提问作者GolDRoger