分析

• 本题的考点：桶排序。

• 分为两步：

（1）使用桶排序，对原数组进行操作，使得1出现在nums[0]的位置上，2出现在nums[1]的位置上，…，n出现在nums[n-1]的位置。因此，如果$0<nums[i] \le n$，则nums[i]应该出现在nums[nums[i] - 1]的位置上。

（2）上述过程结束后，找到第一个不在应在位置上的1到n的数，即当nums[i] != i+1时返回i+1，如果全部满足nums[i] == i+1，则说明整个数组中的元素是1~n，返回n+1即可。

• 参考网址：网址。

代码

• C++

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {

        int n = nums.size();

        // (1) 让所有在1~n中的数据t放置到nums[t - 1]中
        for (int i = 0; i < n; i++) {
            int &t = nums[i];  // t应该放到nums[t - 1]的位置
            while (t > 0 && t <= n && nums[t - 1] != t)
                swap(t, nums[t - 1]);  // 此时下标为t-1的位置正确放置了t, 但是nums[i]换过来的数据不一定是i+1, 因此是while
        }

        // (2) 找出不满足nums[i] == i+1的位置，返回i+1; 如果都满足，返回n+1
        for (int i = 0; i < n; i++)
            if (nums[i] != i + 1)
                return i + 1;
        return n + 1;
    }
};

• Java

class Solution {
    public int firstMissingPositive(int[] nums) {

        int n = nums.length;

        // (1) 让所有在1~n中的数据nums[i]放置到nums[nums[i] - 1]中
        for (int i = 0; i < n; i++) {
            // nums[i]>0且nums[i]<=n时, nums[i]应该放到nums[nums[i] - 1]的位置
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
                swap(nums, i, nums[i] - 1);
        }

        // (2) 找出不满足nums[i] == i+1的位置，返回i+1; 如果都满足，返回n+1
        for (int i = 0; i < n; i++)
            if (nums[i] != i + 1)
                return i + 1;
        return n + 1;
    }

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

时空复杂度分析

• 时间复杂度：$O(n)$。因为每次交换，会将一个数放在正确的位置上，所以总共最多执行n次，所以总时间复杂度$O(n)$。

• 空间复杂度：$O(1)$。使用原数组。