为何要将数值放在索引位置对应的地方？
- 假设数组长度为 n，数组中有 n 个位置 [0, 1, ..., n-1]。正整数序列 [1, 2, ..., n] 的数字与索引位置之间存在对应关系：
  - 数字 1 应该放在索引 0。
  - 数字 2 应该放在索引 1。
  - 数字 n 应该放在索引 n-1。
- 如果我们能够将所有正整数都放在它们对应的位置，那么第一个不满足条件的索引位置就是答案。
为什么选择这种方法，而不是用其他方式？
- 常规的方法，比如先排序再找第一个缺失的正数，时间复杂度为 O(n log n)，不满足题目要求。
- 哈希表可以记录出现的正整数，但需要额外的空间，不满足 O(1) 的空间复杂度要求。
- 索引与数值的对应关系让我们能够直接操作原数组，以 O(n) 的时间和 O(1) 的空间解决问题。

具体步骤

步骤 1：将每个正整数放到对应的位置

遍历数组，对于每个元素 nums[i]：
- 如果 nums[i] 是正整数，且在 [1, n] 范围内（这里 n 是数组长度），并且它没有在正确的位置上（即 nums[i] != nums[nums[i] - 1]），则将它交换到正确的位置。

步骤 2：找到第一个不符合条件的位置

再次遍历数组，检查 nums[i] 是否等于 i + 1。
- 如果 nums[i] != i + 1，说明数字 i + 1 缺失。
- 如果所有位置都符合条件，说明 [1, n] 都存在，返回 n + 1。

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        Solution solution = new Solution();
        int result = solution.firstMissingPositive(nums);
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // Step 1: 原地哈希，将每个数字放到对应的位置
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
            }
        }

        // Step 2: 查找第一个不满足条件的位置
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1; // 返回第一个缺失的正数
            }
        }

        // 如果所有位置都满足条件，返回 n + 1
        return n + 1;
    }

    // 交换数组中的两个元素
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

代码解析

示例：`nums = [3, 4, -1, 1]`

原地哈希：
- 初始数组：[3, 4, -1, 1]
- 第一个元素 3：
  - 交换到索引 2 的位置：[-1, 4, 3, 1]
- 第二个元素 4：
  - 交换到索引 3 的位置：[-1, 1, 3, 4]
- 第二个元素继续处理：将 1 交换到索引 0 的位置：[1, -1, 3, 4]
- 结果数组：[1, -1, 3, 4]
查找结果：
- 遍历 [1, -1, 3, 4]，发现索引 1 的值不等于 2，返回 2。

时间复杂度分析

原地哈希：
- 每个数字最多被交换一次，交换操作的时间复杂度为 O(1)。
- 因此，整个过程的时间复杂度为 O(n)。
遍历查找：
- 再次遍历数组一次，时间复杂度为 O(n)。

总时间复杂度：O(n)。

空间复杂度分析

原地哈希：
- 直接在原数组上操作，未使用额外的存储空间。
辅助变量：
- 只使用了少量的辅助变量（如 temp），空间复杂度为 O(1)。

总空间复杂度：O(1)。

总结

核心思路：利用索引和数值的对应关系，通过交换操作，将数组中的每个正整数尽可能放到正确的位置上。
为什么选择这种方法？
- 排序的时间复杂度为 O(n log n)，哈希表需要额外空间，而这种方法直接操作数组，满足 O(n) 时间和 O(1) 空间的要求。
适用场景：适合处理大规模数据，且需要节省空间的场景。