Leetcode JAVA刷刷站（41）缺失的第一个正数

一、题目概述

二、思路方向

为了找到未排序整数数组中未出现的最小正整数，并满足时间复杂度为 O(n) 和只使用常数级别额外空间的要求，我们可以采用原地哈希（也称为索引哈希）的方法。这个方法的基本思想是将每个数字（如果它在 1 到 n 的范围内，其中 n 是数组的长度）放到它应该在的索引位置上。如果索引位置上的数字不是它本身的值加一（考虑数组索引从 0 开始），那么我们就需要调整它。

具体步骤如下：

遍历数组，对于每个元素 nums[i]：
如果 nums[i] 不在 1 到 n 的范围内，或者 nums[i] 等于 nums[nums[i] - 1]（即已经在正确的位置上），则跳过。
否则，如果 nums[i] 不在 nums[nums[i] - 1] 的位置上，则将 nums[nums[i] - 1] 和 nums[i] 交换。
再次遍历数组，找到第一个不满足 nums[i] = i + 1 的位置 i，则 i + 1 就是未出现的最小正整数。如果所有元素都满足 nums[i] = i + 1，则未出现的最小正整数是 n + 1。

三、代码实现

public class Solution {  public int firstMissingPositive(int[] nums) {  int n = nums.length;  // 第一步：将每个数字放到它应该在的索引位置上（如果它的值在 1 到 n 之间）  for (int i = 0; i < n; i++) {  while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {  // 交换 nums[i] 和 nums[nums[i] - 1]  int temp = nums[i];  nums[i] = nums[nums[i] - 1];  nums[temp - 1] = temp;  }  }  // 第二步：找到第一个不满足 nums[i] = i + 1 的位置  for (int i = 0; i < n; i++) {  if (nums[i] != i + 1) {  return i + 1;  }  }  // 如果没有找到，说明 1 到 n 都出现了，返回 n + 1  return n + 1;  }  public static void main(String[] args) {  Solution solution = new Solution();  int[] nums = {3, 4, -1, 1};  System.out.println(solution.firstMissingPositive(nums)); // 输出 2  int[] nums2 = {4, 3, 2, 7, 8, 2, 3, 1};  System.out.println(solution.firstMissingPositive(nums2)); // 输出 5  }  
}