41. First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer.Example 1:Input: [1,2,0]Output: 3Example 2:Input: [3,4,-1,1]Output: 2Example 3:Input: [7,8,9,11,12]Output: 1Note:Your algorithm should run in O(n) time and uses constant extra space.难度：hard题目：给定一无排序的整数数组，找出丢失的最小正整数。注意：算法时间复杂度为O(n)空间复杂度为常量。思路：清除所有原数组中不在范围［1,n(数组长度)]的值。并将所有index + 1 = nums[index]的数组归位。归位过程中相等的两个元素不用交换（避免无限循环）Runtime: 5 ms, faster than 100.00% of Java online submissions for First Missing Positive.class Solution { public int firstMissingPositive(int[] nums) { if (null == nums || nums.length < 1) { return 1; } int t = 0, n = nums.length; for (int i = 0; i < n; i++) { // make it as zero to avoid array index overflow if (nums[i] <= 0 || nums[i] > n) { nums[i] = 0; } else if ((i + 1) != nums[i] && nums[nums[i] - 1] != nums[i]) { t = nums[nums[i] - 1]; nums[nums[i] - 1] = nums[i]; nums[i–] = t; } } for (int i = 0; i < nums.length; i++) { if ((i + 1) != nums[i]) { return i + 1; } } return n + 1; }}