缺失的第一个正数

题目要求

在这个问题中，我们需要处理一个未排序的整数数组 nums。我们的目标是找到并返回这个数组中没有出现的最小的正整数。这个任务需要在 O(n) 时间复杂度内完成，并且只能使用常数级别的额外空间。

解题思路

要在 O(n) 时间复杂度内解决这个问题，同时又只能使用常数级别的额外空间，我们可以采用原地哈希（in-place hashing）的方法。以下是解题的步骤：

过滤负数和零：首先，我们可以忽略所有负数和零，因为它们不会影响我们寻找最小正整数的结果。
原地哈希：接下来，我们可以遍历数组，尝试将每个正整数放到其值对应的索引位置上。例如，如果我们遇到数字 3，我们就尝试将它放到索引为 2 的位置上（因为数组索引通常是从 0 开始的）。这个步骤中，我们需要注意的是，如果数字大于数组长度，或者要交换的两个数字相同，那么我们就不需要交换。
检查缺失的最小正整数：完成原地哈希后，我们再次遍历数组。这一次，我们检查每个索引位置是否放置了正确的数字。第一个不符合“索引 + 1 等于数字本身”的位置，其索引 + 1 的值就是我们要找的最小的缺失正整数。例如，如果在索引 0 的位置不是数字 1，那么最小的缺失正整数就是 1。
处理特殊情况：如果数组中的所有位置都放置了正确的数字，这意味着数组形如 [1, 2, 3, ..., n]，那么缺失的最小正整数就是 n+1。

通过以上步骤，我们可以在 O(n) 的时间复杂度内找到缺失的最小正整数，同时只使用了常数级别的额外空间，因为我们没有使用额外的数组或数据结构来存储信息。

Golang 版本

package main

import (
	"fmt"
)

func firstMissingPositive(nums []int) int {
	n := len(nums)

	// 将所有的负数转换为n+1（一个肯定不会是答案的数）
	for i := 0; i < n; i++ {
		if nums[i] <= 0 {
			nums[i] = n + 1
		}
	}

	// 使用索引作为哈希键，对于每个数字，如果它在1到n的范围内，就将对应索引位置的数字标记为负数
	for i := 0; i < n; i++ {
		num := abs(nums[i])
		if num <= n {
			nums[num-1] = -abs(nums[num-1])
		}
	}

	// 第一个正数的索引+1就是我们要找的最小正整数
	for i := 0; i < n; i++ {
		if nums[i] > 0 {
			return i + 1
		}
	}

	// 如果所有的数都被标记了，说明数组是连续的1到n，那么答案就是n+1
	return n + 1
}

// abs 返回一个整数的绝对值
func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func main() {
	nums := []int{3, 4, -1, 1}
	fmt.Println("The smallest missing positive integer is:", firstMissingPositive(nums))
}

这段代码实现了上述的解题思路，定义了 firstMissingPositive 函数来找出未排序整数数组中缺失的最小正整数，并在 main 函数中测试了这个功能。函数 abs 用于计算绝对值，以便在原地哈希过程中正确处理数字。

C++版本

#include <iostream>
#include <vector>
#include <algorithm>

int firstMissingPositive(std::vector<int>& nums) {
    int n = nums.size();

    // 将所有的负数和零转换为n+1（一个肯定不会是答案的数）
    for (int& num : nums) {
        if (num <= 0) {
            num = n + 1;
        }
    }

    // 使用索引作为哈希键，对于每个数字，如果它在1到n的范围内，就将对应索引位置的数字标记为负数
    for (int i = 0; i < n; ++i) {
        int num = abs(nums[i]);
        if (num <= n) {
            nums[num - 1] = -abs(nums[num - 1]);
        }
    }

    // 第一个正数的索引+1就是我们要找的最小正整数
    for (int i = 0; i < n; ++i) {
        if (nums[i] > 0) {
            return i + 1;
        }
    }

    // 如果所有的数都被标记了，说明数组是连续的1到n，那么答案就是n+1
    return n + 1;
}

int main() {
    std::vector<int> nums = {3, 4, -1, 1};
    std::cout << "The smallest missing positive integer is: " << firstMissingPositive(nums) << std::endl;
    return 0;
}

这段 C++代码实现了寻找未排序整数数组中缺失的最小正整数的功能。它首先将所有非正整数转换为一个大于数组长度的数，然后通过将存在的正整数对应索引的数值变为负数来标记这些数已经存在。最后，遍历数组，第一个索引位置上数值为正的索引加 1 即为缺失的最小正整数。如果所有数值都被标记为负数，则说明数组中包含了从 1 到 n 的连续整数，因此返回 n+1。

Python 版本

def first_missing_positive(nums):
    n = len(nums)

    # 将所有的负数和零转换为n+1（一个肯定不会是答案的数）
    for i in range(n):
        if nums[i] <= 0:
            nums[i] = n + 1

    # 使用索引作为哈希键，对于每个数字，如果它在1到n的范围内，就将对应索引位置的数字标记为负数
    for i in range(n):
        num = abs(nums[i])
        if num <= n:
            nums[num - 1] = -abs(nums[num - 1])

    # 第一个正数的索引+1就是我们要找的最小正整数
    for i in range(n):
        if nums[i] > 0:
            return i + 1

    # 如果所有的数都被标记了，说明数组是连续的1到n，那么答案就是n+1
    return n + 1

# 测试代码
if __name__ == "__main__":
    nums = [3, 4, -1, 1]
    print("The smallest missing positive integer is:", first_missing_positive(nums))

这段 Python 代码实现了寻找未排序整数数组中缺失的最小正整数的功能。它首先将所有非正整数转换为一个大于数组长度的数，然后通过将存在的正整数对应索引的数值变为负数来标记这些数已经存在。最后，遍历数组，第一个索引位置上数值为正的索引加 1 即为缺失的最小正整数。如果所有数值都被标记为负数，则说明数组中包含了从 1 到 n 的连续整数，因此返回 n+1。

Java 版本

public class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // 将所有的负数和零转换为n+1（一个肯定不会是答案的数）
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }

        // 使用索引作为哈希键，对于每个数字，如果它在1到n的范围内，就将对应索引位置的数字标记为负数
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }

        // 第一个正数的索引+1就是我们要找的最小正整数
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        // 如果所有的数都被标记了，说明数组是连续的1到n，那么答案就是n+1
        return n + 1;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {3, 4, -1, 1};
        System.out.println("The smallest missing positive integer is: " + solution.firstMissingPositive(nums));
    }
}

这段 Java 代码实现了寻找未排序整数数组中缺失的最小正整数的功能。它首先将所有非正整数转换为一个大于数组长度的数，然后通过将存在的正整数对应索引的数值变为负数来标记这些数已经存在。最后，遍历数组，第一个索引位置上数值为正的索引加 1 即为缺失的最小正整数。如果所有数值都被标记为负数，则说明数组中包含了从 1 到 n 的连续整数，因此返回 n+1。

Rust 版本

fn first_missing_positive(nums: &mut Vec<i32>) -> i32 {
    let n = nums.len();

    // 将所有的负数和零转换为n+1（一个肯定不会是答案的数）
    for num in nums.iter_mut() {
        if *num <= 0 {
            *num = n as i32 + 1;
        }
    }

    // 使用索引作为哈希键，对于每个数字，如果它在1到n的范围内，就将对应索引位置的数字标记为负数
    for i in 0..n {
        let num = nums[i].abs();
        if num <= n as i32 {
            let idx = (num - 1) as usize;
            nums[idx] = -nums[idx].abs();
        }
    }

    // 第一个正数的索引+1就是我们要找的最小正整数
    for (i, &num) in nums.iter().enumerate() {
        if num > 0 {
            return (i + 1) as i32;
        }
    }

    // 如果所有的数都被标记了，说明数组是连续的1到n，那么答案就是n+1
    (n as i32) + 1
}

fn main() {
    let mut nums = vec![3, 4, -1, 1];
    println!("The smallest missing positive integer is: {}", first_missing_positive(&mut nums));
}

这段 Rust 代码实现了寻找未排序整数数组中缺失的最小正整数的功能。它首先将所有非正整数转换为一个大于数组长度的数，然后通过将存在的正整数对应索引的数值变为负数来标记这些数已经存在。最后，遍历数组，第一个索引位置上数值为正的索引加 1 即为缺失的最小正整数。如果所有数值都被标记为负数，则说明数组中包含了从 1 到 n 的连续整数，因此返回 n+1。

总结

上述解法采用了一个巧妙的方法来在 O(n)时间复杂度和常数空间复杂度内找到未排序数组中缺失的最小正整数。解法的核心思想是利用数组本身作为哈希表来记录信息。以下是解法的步骤总结：

替换非正数：首先，遍历数组，将所有的非正数（包括零和负数）替换为一个大于数组长度的数（例如 n+1）。这样做的目的是为了确保数组中所有的数都是正数，且不会影响后续的步骤。
标记存在的正数：接着，再次遍历数组，对于每个数 num（绝对值），如果它在 1 到 n 的范围内，就将数组中索引为 num-1 的位置的数标记为负数。这样做相当于记录了 num 这个数已经在数组中出现过。
寻找缺失的最小正数：最后，再次遍历数组，寻找第一个正数出现的位置。由于之前的标记，如果数组中缺少某个数，那么对应的索引位置上的数将不会被标记为负数，因此第一个正数的索引加 1 就是缺失的最小正数。
处理特殊情况：如果数组中的数是从 1 到 n 的连续正整数，那么上述步骤后，所有的数都会被标记为负数。在这种情况下，缺失的最小正整数就是 n+1。

这种解法巧妙地避免了额外空间的使用，同时保证了线性的时间复杂度，是解决这类问题的一个高效算法。

hot-100