Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0]
Output: 3
Example 2:
Input: [3,4,-1,1]
Output: 2
Example 3:
Input: [7,8,9,11,12]
Output: 1
tag: array
method1
在这类找具有连续性质的某个数字时，ｓｅｔ非常好用，而且速度还快，只是要求占用Ｏ（ｎ）的空间
将数组所有数都放进ｈａｓｈｓｅｔ中，然后从１开始查找，当查找不到时证明缺失
public int firstMissingPositive(int[] nums) {HashSet<Integer> set = new HashSet<>();for (int i = 0; i < nums.length; i++) {set.add(nums[i]);}int i = 1;while (set.contains(i))i++;return i;}
method2
为了避免Ｏ（ｎ）的空间使用，最好的办法就是将数字放在它该放的位置，即Ａ［ｉ］＝ｉ＋１，其中负数和大于数组长的数可以不用考虑（反正就让他们放在原位，遍历到那个位置发现不满足，那么自然结果就是那个位置）
难点在理解第二个ｉｆ上，nums[i]相当于ｉ（每个positive number），那么 nums[i]-1就相当于他们在数组中该放的位置，如果不想等，就说明不满足Ａ［ｉ］＝ｉ＋１，因此交换ｉ和nums[i]-1两个位置的值，确保nums[i]这个值在它该在的位置上
public int firstMissingPositive2(int[] nums){int i = 0;while (i < nums.length){if (nums[i] == i+1 || nums[i] <= 0 || nums[i] > nums.length) i++;else if (nums[nums[i] - 1] != nums[i]) swap(nums,i,nums[i]-1);else i++;}int res = 0;while (res < nums.length && nums[res] == res+1){res++;}return res+1;
summary:
- 在查找连续性质的数中,swap往往是避免Ｏ（ｎ）空间的好办法
- set也是