leetcode41_缺失的第一个正数

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

示例 1:

输入: [1,2,0]
输出: 3
示例 2:

输入: [3,4,-1,1]
输出: 2
示例 3:

输入: [7,8,9,11,12]
输出: 1
说明:

你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
 */

/*
 * 题目大意：找到一个未排序序列中的第一个缺失的正数。简而言之，就是看1在不在这个序列中，如果不在的话输出1；
 * 否则看2在不在这个序列中，如果不在的话输出2；否则看3在不在这个序列中

思路：

本题的一个难点就在 要求O(n)时间复杂度  O(1)空间复杂度  不允许申请新的空间

1.先说说O(n)空间复杂度的解法   利用HashSet存放所有的数组元素   然后从1开始  找到第一个不在set里面的元素 就是最小值

2.O(1)空间复杂度的解法

nums[i]代表该数在数组中应该处于第i个位置  对应数组的索引就是i-1  也就是nums[i]-1

举个例子，假设有序列[4,2,6,1,-3]，首先看第一个数4，它正确的位置应该是在序列的第4个位置（位置数从1开始，正确的位置是第一个位置放1，第二个位置放2，第三个位置放3……最后我们只要看哪个位置放的不是理想的数，
那么它就是第一个缺失的正数）。我们将4与第4个位置上的“1”进行交换，序列变成[1,2,6,4,-3]；接着我们还是
看第一个数，现在变成了“1”，它的确在它正确的位置，好了，我们再看第二个数2，也在正确的位置。第三个数6，
本来应该放在第6个位置，可是该序列总共就5个位置，所以不移动；第四个数4在它的正确位置，不动；第五个数是负数，
不动。最后，从前往后看，发现在第三个位置本该出现的3没有出现，所有该序列缺失的第一个正数是3。

     //时间复杂度应为O(n)，并且只能使用常数级别的空间
	 public static int firstMissingPositive(int[] nums) {
		
		 int len=nums.length;
		 for (int i = 0; i < len; i++) {
			 //nums[i]代表该数在数组中应该处于第i个位置  对应数组的索引就是i-1  也就是nums[i]-1
			 //由于负数不考虑  所以nums[i]>0  而nums[i]如果大于数组长度 则也不用交换  
			while (nums[i]>0&&nums[i]<=len&&nums[i]!=nums[nums[i]-1]) {
				swap(nums,i,nums[i]-1);
			}
		}
		 //操作完成之后 遍历 找到nums[i]第一个不等于i+1的点  结果就是i+1
		 for (int i = 0; i < len; i++) {
			if (nums[i]!=i+1) {
				return i+1;
			}
		}
		 //都符合要求了  说明数组的值是 1~nums.length  则返回		 
		 return len+1;        
	    }

	private static void swap(int[] nums, int i, int j) {
		int temp=nums[i];
		nums[i]=nums[j];
		nums[j]=temp;
	}