给定一个无序的整数数组,找出第一个缺失的正整数,整数数组中求出最小值

一道笔试题，记录一下解题思路
题目描述：
给定一个无序整型数组arr,找到数组中未出现的最小整数 。要求时间复杂度为O(N)空间复杂度为O(1)。
示例

nums=[-1,2,3,4] return 1 nums=[1,2,3,4] return 5

分析：
要是不考虑时空间复杂度，可以直接两层循环暴力查找或者先排序后查。

1.初始化两个变量:
left = 0(表示[1~left]的正整数已经找到了合适的位置);

right=n(边界，若超出这个边界则“未出现的最小正整数”必在1~n),

2.假设数组nums为整数1,2,3…n的一个随机排列，那么未出现的最小正整数就是n+1。

nums中有小于1或者大于N的数出现(“不合法”的数)如果[left+1 ~ right]中有一个元素不合法，那么这个right就是减少1，因为最多已经不能放下[1 ~ right]了，最多只能放下[1 ~ right-1]了

代码：

class solution{public int getDisappearNum(int[] nums){int left = 0;int right = nums.length;while (left < right){if (nums[left] == left + 1) //在理想合法的位置{left ++;} else if (nums[left] > right || nums[left] <= left) //不合法 {nums[left] = nums[--right];} else //合法但不在正确位置的元素（把它交换到正确的位置）{//nums[nums[left] - 1]表示nums[left]应该在的正确位置swap(nums, left, nums[left] - 1);}}return left + 1;}private void swap(int[] nums, int a, int b){int tmp = nums[a];nums[a] = nums[b];nums[b] = tmp;}}