缺失的第一个正数-LeetCode刷题 - LeetCode刷题 | Windlinxy's Blog = 沨临 = 记录回忆，分享经验，慢慢进步

# 缺失的第一个正数

41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

如果不考虑时间问题，只考虑空间问题，这题很好做，将数组排序，用一个 count 记一下最小正数就行

	class Solution {
	public int firstMissingPositive(int[] nums) {
	Arrays.sort(nums);
	int count = 1;
	for(int item : nums){
	if(item == count){
	count++;
	}else if(count < item){
	return count;
	}
	}
	return count;
	}
	}

如果不考虑空间问题，只考虑时间问题，需要用到桶

	class Solution {
	public int firstMissingPositive(int[] nums) {
	int len = nums.length;
	int res[] = new int[len+1];
	for(int i : nums){
	if(i > 0 && i<=len)
	res[i] = 1;
	}
	for(int i = 1 ;i<=len;i++){
	if(res[i] == 0){
	return i;
	}
	}
	// 如果循环没返回说明正好数组中的数是 1~n
	return len+1;
	}
	}

时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案就是操作原数组，原地哈希。

对于原数组，将其变为一个 nums[i-1] = i 的形式。

例子：

长度为 4 的数组 {4,2,1,3}，原地哈希后 {1,2,3,4}，每个元素满足 nums[i-1] = i 。
数组 {4, -1, 1, 3}，原地哈希后 {1, -1, 3, 4}，此时遍历找到第一个满足 nums[i-1] != i 的元素返回对应缺失的正数即可。

	public int firstMissingPositive(int[] nums) {
	int n = nums.length;
	for (int i = 0; i < n; i++) {
	// 符合 hash 的条件跳过
	if (i + 1 == nums[i]) {
	continue;
	}
	if (0 < nums[i] && nums[i] <= n && nums[i] != nums[nums[i]-1]) {
	swap(nums, i, nums[i] - 1);
	// 交换后需要再次判断 nums [nums [i]-1]
	i--;
	}
	}
	for (int i = 0; i < n; i++) {
	if (nums[i] != i + 1) {
	return i + 1;
	}
	}
	return n + 1;
	}

	public void swap(int[] arr, int i, int j) {
	if (i != j) {
	arr[i] ^= arr[j];
	arr[j] ^= arr[i];
	arr[i] ^= arr[j];
	}
	}