题解 | #缺失的第一个正整数#

看了leetcode的空间O(1)解法自己写了遍代码，记录一下思路吧 主要是把原来数组当做hash表用的思想，由于如果数组中有空隙，解肯定在[1,n]之间，那么在数组相应的[0,n-1]位置标记这些存在的元素，比如遍历到一个4，那么就把下标为4-1=3的位置的值置为负数，置为负数这个点很巧妙，这个负数不能随意设置一个负数，必须是原来正数的相反数，因为如若不然，会篡改后面的信息。那么这就又引出了问题，数组中原来的负数怎么处理呢，答案是在上述步骤前先置为n+1,超过数组界限，这样不会修改数组中的位置信息,统一初始状态，避免置为相反数时冲突的问题。 给出java实现 public int minNumberDisappeared (int[] nums) { // Map<Integer,Integer> pos=new HashMap<>();

    // write code here
    int len=nums.length;
    for(int i=0;i<len;i++){
        if(nums[i]<=0) nums[i]=len+1;
    }
    for(int i=1;i<len+1;i++){
        int x;
        if(nums[i-1]<0) x=-nums[i-1];
        else x=nums[i-1];
        
        if(x>0 && x<len+1) nums[x-1]=-nums[x-1];
        
    }
    for(int i=0;i<len;i++){
        if(nums[i]>0) return i+1;
    }
    return len+1;
    
}