一. 题目

二. 思路

1. 覆盖哈希

2. 置换

三. 代码

1. 覆盖哈希

class Solution
{
    public int firstMissingPositive(int[] nums)
    {
        int n = nums.length;
        for (int i = 0; i < n; ++i)//将所有<=0的数改为n+1
            if (nums[i] <= 0)
                nums[i] = n + 1;

        for (int i = 0; i < n; ++i)//标记
        {
            int num = Math.abs(nums[i]);
            if (num <= n) nums[num - 1] = -Math.abs(nums[num - 1]);
        }

        for (int i = 0; i < n; ++i)
            if (nums[i] > 0)
                return i + 1;
        return n + 1;
    }
}

2. 置换

class Solution
{
    public int firstMissingPositive(int[] nums)
    {
        int n = nums.length;
        for (int i = 0; i < n; ++i)
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
            {
                int t = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = t;
            }
        for (int i = 0; i < n; ++i)
            if (i + 1 != nums[i])
                return i + 1;
        return n + 1;
    }
}