完整题目描述

在一个未排序的整数数组中，找到丢失的第一个正整数。数组的范围在 [-2^31, 2^31 - 1] 内，且数组中除了一个正整数丢失以外，其他数字均只出现一次，并且数组中的每个数字都在范围 [1, n] 内（其中 n 是数组的长度），但请注意，数组中的 0 并不属于这个范围。

例如，数组 [3, 4, -1, 1] 中丢失的第一个正整数是 2。数组 [1, 2, 0] 没有丢失正整数，返回 n+1（因为题目中说明数组中的数字都在范围 [1, n] 内，所以若未丢失任何正整数，则默认丢失的是 n+1）。

PHP 示例代码

function findFirstMissingPositive($nums) {
    $n = count($nums);
    // Step 1: 将所有非正整数替换为 n+1，保证后续操作只处理正整数
    for ($i = 0; $i < $n; $i++) {
        if ($nums[$i] <= 0 || $nums[$i] > $n) {
            $nums[$i] = $n + 1;
        }
    }

    // Step 2: 利用数组索引作为标记，负数索引不处理
    for ($i = 0; $i < $n; $i++) {
        $index = abs($nums[$i]);
        if ($index <= $n) {
            // 将对应的索引位置变为负数，表示该数字已出现
            $nums[$index - 1] = -$abs($nums[$index - 1]);
        }
    }

    // Step 3: 找到第一个非负数的索引，即为丢失的正整数
    for ($i = 0; $i < $n; $i++) {
        if ($nums[$i] > 0) {
            return $i + 1;
        }
    }

    // 如果所有正整数都出现了，则返回 n+1
    return $n + 1;
}

// 注意：PHP 中没有内置 abs 函数取绝对值时改变原变量的功能，
// 这里的 `-abs($nums[$index - 1])` 是为了示例说明，实际中应该使用其他方式标记
// 例如，可以先存一个原数组的副本，然后再去标记

Python 示例代码

def findFirstMissingPositive(nums):
    n = len(nums)
    # Step 1: 将所有非正整数替换为 n+1
    for i in range(n):
        if nums[i] <= 0 or nums[i] > n:
            nums[i] = n + 1

    # Step 2: 使用数组索引作为标记
    for i in range(n):
        num = abs(nums[i])
        if 1 <= num <= n:
            nums[num - 1] = -abs(nums[num - 1])

    # Step 3: 找到第一个非负数的索引
    for i in range(n):
        if nums[i] > 0:
            return i + 1

    # 所有正整数都存在，返回 n+1
    return n + 1

JavaScript 示例代码

function findFirstMissingPositive(nums) {
    const n = nums.length;
    // Step 1: 替换非正整数
    for (let i = 0; i < n; i++) {
        if (nums[i] <= 0 || nums[i] > n) {
            nums[i] = n + 1;
        }
    }

    // Step 2: 使用数组索引作为标记
    for (let i = 0; i < n; i++) {
        const index = Math.abs(nums[i]) - 1;
        if (index < n && nums[index] > 0) {
            nums[index] = -nums[index];
        }
    }

    // Step 3: 找到第一个非负数的索引
    for (let i = 0; i < n; i++) {
        if (nums[i] > 0) {
            return i + 1;
        }
    }

    // 所有正整数都存在，返回 n+1
    return n + 1;
}

码小课：在码小课网站中，你可以找到更多关于算法和数据结构的详细解析与实战案例，帮助你提升编程技能，解决复杂问题。