41. 缺失的第一个正数

• 题号：41
• 来源：LeetCode
• 难度：困难
• 标签：数组 原地算法 哈希表
• 语言：TypeScript · Python
• 解法：2 个
• 作者：lmliheng
• 最近更新：2026-09-29

TypeScript

TypeScript · O(n) 时间 · O(1) 空间 · 更新于 2026-09-27

把 x 交换到下标 x-1，再找首个错位处

/**
 * @difficulty hard
 * @tags 数组,原地算法,哈希表
 * @time O(n)
 * @space O(1)
 * @note 把 x 交换到下标 x-1，再找首个错位处
 * @41. 缺失的第一个正数
 * 
 * 实现时间复杂度为 O(n) 并且只使用常数级别额外空间
 */

/**
 * 
 * @
 * 时间O(n),空间O(n)
 */
function firstMissingPositive(nums: number[]) {
    let n=nums.length
    let set=new Set(nums) //n
    for(let i=1;i<n+2;i++){ //n
        if(!set.has(i)){
            return i
        }
    }
};

/**
 * 
 * @原地
 * 时间O(n),空间O(1)
 */
function firstMissingPositive1(nums: number[]): number {
    const n = nums.length;
    
    // 将每个正整数放到它应该在的位置上（值 x 放在索引 x-1）
    for (let i = 0; i < n; i++) {
        // 当前位置的值在 [1, n] 范围内，且没在正确位置上时进行交换
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
            // 交换 nums[i] 和 nums[nums[i] - 1]
            const temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }
    
    // 遍历找出第一个不在正确位置上的数
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }
    // 如果都在正确位置上，则缺失的是 n+1
    return n + 1;
}

源码：ts/leetcode/41. 缺失的第一个正数.ts

Python

Python · O(n) 时间 · O(n) 空间 · 更新于 2026-09-29

集合去重后从 1 起找第一个缺失的正数

"""
@difficulty hard
@tags 数组,哈希表
@time O(n)
@space O(n)
@note 集合去重后从 1 起找第一个缺失的正数
41. 缺失的第一个正数
"""
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n=len(nums)
        set1=set(nums)
        # [1]的情况
        for i in range(1,n+2):
            if not i in set1:
                return i

源码：python/leetcode/hot100/17.py

---

在 GitHub 上查看题目所在目录：lmliheng/algorithm