php - 如何使用 PHP 解决此代码测试？

Question

我第一次进行代码测试，30分钟没有解决这个问题。请您给我一个解决此代码测试的答案吗？

写一个函数：

function solution($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

Answer 1

我确信有一种更有效的方法来完成它，但这里有一些东西可以让你继续前进。它仍然会循环多达 100,000 次，这是相当多的。

function solution($array) {
    $i = 1;
    while (in_array($i, $array)) $i++;
    return $i;
}

编辑：这是一个更优化的解决方案，不使用in_array：

function solution($array) {
    
    // sort from smallest to largest
    sort($array);
    
    // try to find a positive break in the sequence
    $last = 0;
    if (end($array) > 0) {
        foreach ($array as $current) {
            if ($current == $last) continue; // duplicate
            if ($current != $last + 1 && $current > 0) break;
            $last = $current;
        }
    }
    
    return $last + 1;
}