41. First Missing Positive

O(n) time O(1) space
负号法

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i, x in enumerate(nums):
            if x < 1 or x > n:
                nums[i] = n + 1
        for x in nums:
            x = abs(x)
            if 0 < x <= n:
                nums[x - 1] = -abs(nums[x - 1]);
        for i, x in enumerate(nums):
            if x > 0:
                return i + 1
        return n + 1

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int &x : nums) {
            if (x < 1 || x > n) {
                x = n + 1;
            }
        }
        for (int x : nums) {
            x = abs(x);
            if (0 < x && x <= n) {
                nums[x - 1] = -abs(nums[x - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) return i + 1;
        }
        return n + 1;
    }
};

类似桶排序，每个数都应该放在对应的位置，即 nums[i] == nums[nums[i] - 1]，所以不停交换数，尽可能把每个数挪到对应的位置

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            while 0 < nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1] # 注意不能写成nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]因为从左到右赋值，nums[i]先被修改，nums[nums[i] - 1]的新值是错的！！必要时可以考虑加一个中间变量t来swap
        for i, x in enumerate(nums):
            if x != i + 1:
                return i + 1
        return n + 1

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) { // 交换的条件，nums[i]必须在(0, n]之间，而且被交换的数不能等于nums[i]，否则会造成死循环
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < n; ++i) { // 查找第一个不在对应位置的数
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
};