不在数组里的最小正整数

//对于每个数i调整到i-1位置，当然调整后还要接着判断。
//最后重头扫一遍，发现第一个a[i]!=i+1位置的就返回i+1；
class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        for(int i=0;i<n;i++){
            if(A[i]>=1&&A[i]<=n&&A[A[i]-1]!=A[i]) 
                swap(A[i],A[A[i]-1]),i--;   
        }
        for(int i=0;i<n;i++)
            if(A[i]!=i+1) return i+1;
        return n+1;
    }
};

草鸡简单

public int firstMissingPositive(int[] A) {
        if (A == null || A.length == 0)  // 防止越界
            return 1;
        for (int i = 0; i < A.length; i++) {
            //    A[i] - 1 < A.length 超出范围不交换    A[i] != A[A[i] - 1] 相等不交换
            while (A[i] > 0 && A[i] != i + 1 && A[i] - 1 < A.length && A[i] != A[A[i] - 1]) {
                swap(A, i, A[i] - 1);
            }

        }
        for (int i = 0; i < A.length; i++) {
            if (A[i] != i + 1) {
                return i + 1;  // 第一个不相等就返回
            }
        }
        return A[A.length - 1] + 1;  // 数组交换后是有序正数,就返回最大 + 1
    }

    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

import java.util.*;
public class Solution {
    public int firstMissingPositive(int[] A) {
        if(A.length == 0 ) return 1;
        int tmp = 1;
        Arrays.sort(A);
        for(int i: A){
            if(i>=0 && tmp >= i){
                tmp= i+1;
            }
        }
        return tmp;
    }
}

sort的时间复杂度是O(nlogn)...但是可以很好地插空求到需要的返回值 偷懒一时爽一直偷懒一直爽！

import java.util.ArrayList;

public class Solution {
    /*解题思路：先将数组存入Arraylist中，因为这样遍历数组中的任何一个元素的时间变成O(1),即以空间换取时间。
    步骤：（1）遍历数组，找到最大值max，并将数组存入Arraylist中,时间复杂度为O(n)
         （2）遍历从正整数1到最大值max之间的数，并判断Arraylist中是否包含该数。若不包含该数字，则该数字就是第一个缺失的正整数；
         若循环走到底，即Arraylist包含了1到max之间所有数，则第一个缺失数字就是max后一个数字，即max+1.时间复杂度为O(n)*/
    public int firstMissingPositive(int[] A) {
        if(A.length == 0)
            return 1;
        ArrayList<Integer> list = new ArrayList<>();
        int max = 0;
            //步骤（1）
        for(int i = 0;i < A.length;i ++){
            list.add(A[i]);
            if(A[i] > max){
                max = A[i];
            }
        }
           //步骤（2）
        for(int i = 1;i <= max;i ++){
            if(!list.contains(i))
                return i;
        }
        return max + 1;
    }
}

class Solution {
public:
    int firstMissingPositive(int A[], int n) 
    {
        if(A==nullptr || n<=0)
        return 1;
    unordered_map<int,int> intMap;
    for(int i=0;i<n;i++)
        intMap[A[i]] = i;
    int max = *max_element(A,A+n);
    for(int i=1;i<=max;i++)
    {
        if(intMap.find(i) == intMap.end())
            return i;
    }
    return max+1;
    }
};

class Solution {
public:
int firstMissingPositive(int A[], int n) 
{
	vector<int> v(n+1, 0);
	for (int i = 0; i<n; ++i)
	{
		if (A[i] <= n && A[i] >= 0)
			v[A[i]] ++;
	}
	for (int i = 1; i <= n; ++i)
	{
		if (v[i] == 0)
			return i;
	}
	return n + 1;
}
};

//使用hash,n个数只需要保存1-n的个数，因为如果缺少一定是在这些数中间，否则就是n+1

/*
说一下思路吧
遍历数组，如果数组的元素k范围是[1,length]，与nums[k-1]的元素交换位置
处理结束，数组中i下标的元素为i+1（即指向下一元素），第一个不满足该条件的元素就是所求元素

表述起来可能有点抽象，结合代码画个图理解的更快
*/

public int firstMissingPositive(int[] nums) {
		if (nums == null || nums.length < 1)
			return 1;
		int i = 0;
		while (i < nums.length) {
			if (nums[i] == i + 1 || nums[i] <= 0 || nums[i] > nums.length)
				i++;
			// 防止死循环.条件不能是else if (nums[i] != i + 1)
			//比如[1,1]会引起死循环
			else if (nums[nums[i] - 1] != nums[i])
				swap(nums, i, nums[i] - 1);
			else
				i++;
		}

		i = 0;
		while (i < nums.length && nums[i] == i + 1)
			i++;
		return i + 1;
	}

	private void swap(int[] nums, int i, int j) {
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}

public class Solution {
    public int firstMissingPositive(int[] A) {
		if(A.length == 0) return 1;
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < A.length; i ++) {
			max = max > A[i] ? max : A[i];
		}
		boolean[] flag = new boolean[max + 1];
		for (int i = 0; i < A.length; i ++) {
			if(A[i] > 0) flag[A[i]] = true;
		}
		for (int i = 1; i < flag.length; i ++) {
			if( ! flag[i]) return i;
		}
		return max + 1;
	}
}

Put each number in its right place.

For example:

When we find 5, then swap it with A[4].

At last, the first place where its number is not right, return the place + 1.

class Solution {
public:
    int firstMissingPositive(int A[], int n)
    {
        for(int i = 0; i < n; ++ i)
            while(A[i] > 0 && A[i] <= n && A[A[i] - 1] != A[i])
                swap(A[i], A[A[i] - 1]);
        
        for(int i = 0; i < n; ++ i)
            if(A[i] != i + 1)
                return i + 1;
        
        return n + 1;
    }
};

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        for(int i=0;i<n;i++)
        {
        	int x = A[i];
        	while(x>0 && x<=n && A[x-1]!=x)
        		swap(x, A[x-1]);
		}
    	
    	for(int i=0;i<n;i++)
    		if(A[i] != i+1)
    			return i+1;
    	
		return n+1;
    }
};

cout<<"bilibili";

import java.util.*;


public class Solution {
    /**
     * 
     * @param A int整型一维数组 
     * @return int整型
     */
    public int firstMissingPositive (int[] A) {
        int min = 1;
        if (A == null || A.length == 0){
            return min;
        }
        Arrays.sort(A);
        int len = A.length;
        for (int i = 0; i < len; i++) {
            if ( A[i] == min){//找到当前值就加1
                 min++;
            }
        }
        return min;
    }
}

int firstMissingPositive(int* A, int n) {
        // write code here
        //最终一个整数i被填写入A[i-1]
        //若一个位置的数不属于这，那么填充到它属于的位置，并不断下去直到 完成闭环
        
        for(int i=0;i<n;i++)
        {
            
            if(A[i]==i+1)  
                continue;
            int k=A[i];//其目标填充位置
            while(k>0 && k-1<n && A[k-1]!=k)  //注意如果k值过大 将超出范围
            {
                int tmp=A[k-1];//记录下目标位置的值
                A[k-1]=k;
                k=tmp;

            } 
            
        }
        
        for(int i=0;i<n;i++)
        {
            if(A[i]!=i+1)
                return i+1;
        }
        return n+1;

        
    }

public int firstMissingPositive (int[] A) {
        int[] temp = new int[A.length];
        for(int i=0;i<A.length;i++){
            if(A[i] > 0 && A[i] <= A.length){
                temp[A[i]-1] = A[i];
            }
        }
        for(int i=0;i<temp.length;i++){
            if(temp[i]==0){
                return i+1;
            }
        }
        return A.length+1;
    }

public int firstMissingPositive (int[] A) {
        if(A == null || A.length == 0) {
            return 1;
        }
        for(int i = 0; i < A.length; i++) {
            int v = A[i];
            while(v > 0 && v <= A.length && v != A[v - 1]) {
                swap(A, i, v - 1);
                v = A[i];
            }
        }
        for(int i = 0; i < A.length; i++) {
            if(A[i] != i + 1) {
                return i + 1;
            }
        }
        return A.length + 1;
    }
    
    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }