给定一个无序数组arr，找到数组中未出现的最小正整数
例如arr = [-1, 2, 3, 4]。返回1
arr = [1, 2, 3, 4]。返回5
[要求]
时间复杂度为O(n)O(n)，空间复杂度为O(1)O(1)
示例1
输入 [-1,2,3,4] 返回值 1 import java.util.*;public class Solution { /** * 原地哈希，把数组中取值在1到n的数放到对应的位置， * 比如1放到0的位置，2放到1的位置，……n放到n-1的位置，然后遍历重置后的数组， * 若i下标位置不是i+1，则i+1就是那个最小的正整数，若1到n位置都对的上， * 说明最小的正整数是n+1。 * @param args */ public int minNumberdisappered (int[] arr) { int len = arr.length; for(int i=0;i<len;i++){ //arr[arr[i]-1] == arr[i]代表数组中元素的hash位置-1后还是arr[i]的为位置 //如:5431 i=1时在while里经历2次循环后变为1 5 3 4 然后i=2 此时arr[arr[i]-1]=arr[2] = arr[2]此时代表arr数组元素3的位置,存放在hash位置也是arr[2],即:不用交换位置 while(arr[i] >=1 && arr[i] <= len && arr[arr[i]-1] != arr[i]){ //交换arr[i]-1和i位置的元素 即按照从小到大顺序 在hash数组中存储元素 swap(arr,arr[i]-1,i); } } for(int j=0;j<len;j++){ if(arr[j]!=j+1){ return j+1; } } //若1到n位置都对的上，说明最小的正整数是n+1 return len+1; } public void swap(int[] arr,int sourcePos,int targetPos){ int temp = arr[sourcePos]; arr[sourcePos] = arr[targetPos]; arr[targetPos] = temp; }}