Hard

题目描述

给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的算法。

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正整数 1 没有出现。

提示：

  • 1 <= nums.length <= 10^5
  • -2^31 <= nums[i] <= 2^31 - 1

解题思路

这是一个经典的数组问题，需要在 O(n) 时间和 O(1) 空间复杂度下解决。

核心思路： 对于长度为 n 的数组，第一个缺失的正数一定在范围 [1, n+1] 内。我们可以利用数组本身作为哈希表来标记数字的存在性。

算法步骤：

  1. 预处理：将所有非正数和大于 n 的数替换为一个超出范围的值（如 n+1）
  2. 标记存在性：遍历数组，对于每个数字 x，将 nums[|x|-1] 标记为负数（如果还不是负数的话）
  3. 查找结果：再次遍历数组，第一个正数的位置 i 对应的答案就是 i+1

关键技巧：

  • 使用负号来标记数字的存在，避免使用额外空间
  • 处理边界情况：负数、0、超出范围的数

时间复杂度： O(n) - 需要遍历数组3次 空间复杂度： O(1) - 只使用常数级别的额外空间

这种方法巧妙地利用了数组索引和值的对应关系，是解决此类问题的经典技巧。

代码实现

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        
        // 第一步：将所有非正数和大于n的数替换为n+1
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1;
            }
        }
        
        // 第二步：使用负号标记存在的数字
        for (int i = 0; i < n; i++) {
            int num = abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -abs(nums[num - 1]);
            }
        }
        
        // 第三步：找到第一个正数的位置
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        
        return n + 1;
    }
};

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 第一步：将所有非正数和大于n的数替换为n+1
        for i in range(n):
            if nums[i] <= 0 or nums[i] > n:
                nums[i] = n + 1
        
        # 第二步：使用负号标记存在的数字
        for i in range(n):
            num = abs(nums[i])
            if num <= n:
                nums[num - 1] = -abs(nums[num - 1])
        
        # 第三步：找到第一个正数的位置
        for i in range(n):
            if nums[i] > 0:
                return i + 1
        
        return n + 1

public class Solution {
    public int FirstMissingPositive(int[] nums) {
        int n = nums.Length;
        
        // 第一步：将所有非正数和大于n的数替换为n+1
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1;
            }
        }
        
        // 第二步：使用负号标记存在的数字
        for (int i = 0; i < n; i++) {
            int num = Math.Abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.Abs(nums[num - 1]);
            }
        }
        
        // 第三步：找到第一个正数的位置
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        
        return n + 1;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    const n = nums.length;
    
    // 第一步：将所有非正数和大于n的数替换为n+1
    for (let i = 0; i < n; i++) {
        if (nums[i] <= 0 || nums[i] > n) {
            nums[i] = n + 1;
        }
    }
    
    // 第二步：使用负号标记存在的数字
    for (let i = 0; i < n; i++) {
        const num = Math.abs(nums[i]);
        if (num <= n) {
            nums[num - 1] = -Math.abs(nums[num - 1]);
        }
    }
    
    // 第三步：找到第一个正数的位置
    for (let i = 0; i < n; i++) {
        if (nums[i] > 0) {
            return i + 1;
        }
    }
    
    return n + 1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组3次，每次都是O(n)
空间复杂度O(1)只使用常数级别的额外空间，原地修改数组

相关题目