0041.缺失的第一个正数

https://leetcode.cn/problems/first-missing-positive/

方法一：置换

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

对于每一个位置的数 $nums[i]$, 我们可以将其与 $nums[nums[i]-1]$ 进行交换，直到 $nums[i] = nums[nums[i]-1]$ 或者 $nums[i] \leq 0$ 或者 $nums[i] > n$。

func firstMissingPositive(nums []int) int {
	n := len(nums)
	for i := 0; i < n; i++ {
		for nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i]-1] {
			nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
		}
	}
	for i := 0; i < n; i++ {
		if nums[i] != i+1 {
			return i + 1
		}
	}
	return n + 1
}

impl Solution {
    pub fn first_missing_positive(nums: Vec<i32>) -> i32 {
        let n = nums.len() as i32;
        let mut nums = nums;
        for i in 0..nums.len() {
            while nums[i] > 0 && nums[i] <= n && nums[i] != nums[(nums[i] - 1) as usize] {
                let idx = (nums[i] - 1) as usize;
                let tmp = nums[idx];
                nums[idx] = nums[i];
                nums[i] = tmp;
            }
        }
        for i in 0..nums.len() {
            if nums[i] != (i + 1) as i32 {
                return (i + 1) as i32;
            }
        }
        n + 1
    }
}

方法二：哈希

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

func firstMissingPositive(nums []int) int {
	n := len(nums)
	for i := 0; i < n; i++ {
		if nums[i] <= 0 {
			nums[i] = n + 1
		}
	}
	for i := 0; i < n; i++ {
		v := abs(nums[i])
		if v <= n {
			nums[v-1] = -abs(nums[v-1])
		}
	}
	for i := 0; i < n; i++ {
		if nums[i] > 0 {
			return i + 1
		}
	}
	return n + 1
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}