LeetCode 41. 缺失的第一个正数

Categories:

Tags:

题目描述
思路分析
1. 解法一：原地哈希（推荐）
相似题目

题目描述

✅ 41. 缺失的第一个正数

思路分析

解法一：原地哈希（推荐）

核心思路：

对于长度为 n 的数组，缺失的第一个正数必定在 [1, n+1] 范围内。

利用数组本身作为哈希表，将值 x（满足 1 ≤ x ≤ n）放到下标 x-1 的位置（即 nums[x-1] = x）。

两轮扫描：

原地置换：遍历每个位置 i，用 while 循环不断将 nums[i] 换到它「应该在」的位置 nums[i]-1，直到无法继续置换（值越界或目标位置已正确）

查找答案：再次遍历，找到第一个 nums[i] != i+1 的位置，返回 i+1；若全部正确返回 n+1

关键：while 循环终止条件 nums[nums[i]-1] != nums[i]，避免重复值死循环。

举例：[3, 4, -1, 1] → 置换后 [1, -1, 3, 4] → 找到 nums[1] = -1 ≠ 2，返回 2。

复杂度分析：

时间复杂度：O(n)，虽然有嵌套循环，但每个元素最多被交换一次

空间复杂度：O(1)，原地操作，不使用额外空间

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        // 将每个元素放到对应下标位置（值 x 放到 nums[x-1]）
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int tmp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = tmp;
            }
        }
        // 找第一个不在正确位置的元素
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

func firstMissingPositive(nums []int) int {
	n := len(nums)
	// 将每个元素放到对应下标位置（值 x 放到 nums[x-1]）
	for i := 0; i < n; i++ {
		for nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
			nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
		}
	}
	// 找第一个不在正确位置的元素
	for i := 0; i < n; i++ {
		if nums[i] != i+1 {
			return i + 1
		}
	}
	return n + 1
}

相似题目

题目	难度	考察点
268. 丢失的数字	简单	原地哈希/数学求和
287. 寻找重复数	中等	原地标记/快慢指针
448. 找到所有数组中消失的数字	简单	原地标记缺失值
442. 数组中重复的数据	中等	原地哈希标记
765. 情侣牵手	困难	原地置换思想
645. 错误的集合	简单	原地哈希找重复和缺失

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/86507666