书籍数组中未出现的最小正整数(8)0812

题目：

给定一个无序整型数组arr，找到数组中未出现的最小正整数。

举例：

arr=[-1,2,3,4]。返回1。

arr=[1,2,3,4]。返回5。

1、在遍历arr之前先生成两个变量。变量l表示遍历到目前为止，数组arr已经包含的正整数范围是[1,l],所以没有开始遍历之前令l=0，表示arr目前没有包含任何正整数。变量r表示遍历到目前位置，在后续出现最优状况的情况下，arr可能包含的正整数范围是[l,r]，所以没有开始遍历之前，令r=N，因为还没有开始遍历，所以后续出现的最优状况是arr包含1~N所有整数。r同时表示arr当前的结束位置。

2、从左到有遍历arr，遍历到位置l，位置l的数为arr[l]。

3、如果arr[l] == l + 1。没有遍历arr[l]之前，arr已经包含的正整数范围是[1,l],此时出现了arr[l] == l+1的情况，所以arr包含的正整数范围可以扩到[1,l+1],即令l++。然后重复步骤2。

4、如果arr[l] <=1。没有遍历arr[l]之前，arr在后续最优的情况下可能包含的正整数范围是[l,r]，已经包含的正整数范围是[1,l]所以需要[l+1,r]上的数。而此时出现了arr[l] <=1,说明[l+1,r]范围上的数少了一个，所以arr在后续最优的情况下，可能包含的正整数范围缩小了，变为[l,r-1]，此时把arr最后位置的数(arr[r-1])放在位置l上，下一步检查这个数，然后令r--。重复步骤2。

5、如果arr[l]>r,与步骤4同理，把arr最后位置的数(arr[r-1])放在位置l上，下一步检查这个数，然后令r--，重复步骤2。

6、如果arr[arr[l]-1] == arr[l]。如果步骤4喝步骤5没中，说明arr[l]是在[l+1,r]范围上的数，而且这哥数应该放在arr[l]-1位置上。可是此时发现arr[l]-1位置上的数已经是arr[l],说明出现了两个arr[l]，既然在[l+1,r]上出现了重复值，那么[l+1,r]范围上的数又少了一个，所以与步骤4和步骤5一样，把arr最后位置的数(arr[r-1])放在位置l上，下一步检查这个数，然后令r--。重复步骤2。

7、如果步骤4、步骤5和步骤6都没中，说明发现了[l+r,r]范围上的数，并且此时并未发现重复。那么arr[l]应该放到arr[l]-1位置上，所以把l位置的数和arr[l]-1位置上的数交换，下一步继续遍历l位置上的数。重复步骤2。

8、最终l位置和r位置会碰在一起(l==r),arr已经包含的正整数范围是[1,l]返回l+1即可。

public int minssNum(int[] arr){int l = 0;int r = arr.length;while(l < r){if(arr[l] == l + 1){l++;}else if(arr[l] <= 1 || arr[l] > r || arr[arr[l]-1] == arr[l]){arr[l] == arr[--r];}else{swap(arr,l,arr[l] - 1);}}return l + 1;
}