本文详解如何用php以o(n)时间复杂度、简洁代码实现codility“missing integer”问题，避开排序陷阱，通过哈希映射法确保100%正确率与最优性能。
本文详解如何用php以o(n)时间复杂度、简洁代码实现codility“missing integer”问题，避开排序陷阱，通过哈希映射法确保100%正确率与最优性能。
Codility的“Missing Integer”是一道经典算法题：给定一个整数数组 $A$，要求找出未在数组中出现的最小正整数（即最小的 $x \in \mathbb{Z}^+$ 使得 $x \notin A$）。例如，输入 [1, 3, 6, 4, 1, 2] 应返回 5；输入 [-1, -3] 应返回 1；输入 [1, 2, 3] 则返回 4。
原始实现使用双重循环加 sort()，时间复杂度达 $O(N \log N + N^2)$，不仅逻辑冗余（外层 $k$ 无限递增+内层线性查找），且在大规模数据下极易超时——这正是其仅获66%分数的根本原因。
✅ 最优解核心思想：空间换时间
利用PHP关联数组（哈希表）的 $O(1)$ 查找特性，将原数组值作为键构建查找集合，再从1开始逐个检查是否存在。该方案时间复杂度为 $O(N)$（一次遍历建集 + 最坏 $N+1$ 次检查），空间复杂度 $O(N)$，简洁、健壮、100%通过所有测试用例（包括边界情况如全负数、空数组、含重复元素等）。
以下是推荐实现：
function solution($A) {
// 将数组值转为键，构建O(1)查找集合（自动去重，忽略负数/零不影响逻辑）
$set = array_flip($A);
// 从小到大检查1, 2, 3... 是否缺失
for ($n = 1; ; ++$n) {
if (!isset($set[$n])) {
return $n;
}
}
}? 关键说明与注意事项：
立即学习“PHP免费学习笔记（深入）”；
- array_flip($A) 将原数组的值作为新数组的键，值设为原键（通常为索引）。由于我们只关心“某正整数是否存在”，键的存在性（isset()）即代表该数在原数组中出现过；重复值被自动合并，无副作用。
- 循环从 $n = 1 开始，严格按正整数升序检查，首次未命中即为答案，逻辑清晰无遗漏。
- 不需预处理过滤负数或零——isset($set[$n]) 对 $n ≤ 0 本就不成立，但循环不涉及它们，故完全安全。
- 即使数组含极大正整数（如 10^9），最坏情况下也只需检查至 count($A) + 1（鸽巢原理：若前 $N$ 个正整数全存在，则答案必为 $N+1$），实际运行极快。
? 进阶提示（可选优化）：
若极端关注内存，可先扫描一次获取正整数范围上限（如 max(1, count($A)+1)），将循环限制在此范围内，但对Codility测试集非必需——当前解法已足够优雅高效。
总结：摒弃低效排序与嵌套查找，拥抱哈希集合思维，是解决此类“存在性+最小化”问题的通用范式。此方案代码仅5行，语义直白，性能稳定，是PHP工程师应掌握的标准解法。
