题目地址

https://leetcode-cn.com/problems/first-missing-positive/

题目描述

Given an unsorted integer array nums, find the smallest missing positive integer.

Follow up: Could you implement an algorithm that runs in O(n) time and uses constant extra space.?

Example 1:

Input: nums = [1,2,0]
Output: 3

Example 2:

Input: nums = [3,4,-1,1]
Output: 2

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1

Constraints:

• 0 <= nums.length <= 300
• -2^31 <= nums[i] <= 2^31 - 1

思路

本题要求O(n)的时间复杂度和常数的空间复杂度，这导致我们不能用排序，排序至少也要nlogn。
如果借用哈希表，我们的空间复杂度又不满足要求。
因此我们借用哈希表的思路，然后借用原数组的空间实现本题。

如果数字1出现了我们就把第一个数设置为负数，2出现了就将第二个数组设置为负数，最后第一个非负数的位置就是我们缺失的值的位置了。

题解

class Solution {public int firstMissingPositive(int[] nums) {boolean no_one = true;for(int i=0;i<nums.length;++i){if(nums[i]==1) no_one = false;if(nums[i]<=0||nums[i]>nums.length)nums[i] = 1;}int i;if(no_one) return 1;//现在数组里全是正数for(i=0;i<nums.length;++i){//将出现的数的索引处的值改为负数，表示有了nums[Math.abs(nums[i])-1] = -Math.abs(nums[Math.abs(nums[i])-1]); }for(i=0;i<nums.length;++i){if(nums[i]>0) break; }return i+1;}
}