wordpress 网站图标设置电子产品网站

给你一个未排序的整数数组 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 没有出现。

解题思路

方法一： 

        先使用Arrays.sort()方法排序后使用二分查找，时间复杂度O(nlogn)不满足题目要求

方法二：

        将数组存储到哈希集合中，后在遍历确认当前数containsKey()是否存在集合中，空间复杂度O(n)，不满足题目要求

方法三：

        将数组当作哈希表存储，将每个值存到数组对应位置中，如值1存到数组0号索引中，值2存到数组1号索引中，依次类推，若是当前位置的值不是应该对应的值，则找到第一个缺失的正数，若到最后一个还没找到，则数组长度为第一个缺失的值。

解题

        由于方法一、方法二不满足题目要求，使用方法三解决，附上代码

class Solution {  /**  * 找到数组中第一个缺失的正整数  *  * @param nums 输入的整数数组  * @return 数组中第一个缺失的正整数  */  public int firstMissingPositive(int[] nums) {  int len = nums.length;  // 第一步：将所有不在1到len范围内的元素，以及重复的元素（通过交换到正确的位置来消除重复）进行处理  // 这个过程会确保每个位置i（0到len-1）上的元素，要么是nums[i] = i + 1，要么是nums[i] <= 0或者nums[i] > len  for (int i = 0; i < len; i++) {  //使用while要确保当前位置的值不用移动了，可能要移动多次while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {  swap(nums, nums[i] - 1, i);  }  }  // 第二步：遍历数组，找到第一个不满足nums[i] = i + 1的位置  // 如果存在这样的位置，那么i + 1就是第一个缺失的正整数  // 如果遍历完整个数组都没有找到这样的位置，说明数组包含了从1到len的所有正整数，因此缺失的第一个正整数是len + 1  for (int i = 0; i < len; i++) {  if (nums[i] != i + 1) {  return i + 1;  }  }  // 如果数组完整包含了从1到len的所有正整数，则返回len + 1  return len + 1;  }  /**  * 交换数组中两个元素的位置  *  * @param nums 整数数组  * @param a    要交换的第一个元素的索引  * @param b    要交换的第二个元素的索引  */  void swap(int[] nums, int a, int b) {  int tmp = nums[a];  nums[a] = nums[b];  nums[b] = tmp;  }  
}