leetcode41：缺失的第一个正数

题目链接

leetcode

题目描述

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 且只使用常数级别额外空间的解决方案。

C++ 代码

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

void printArray(const vector<int>& nums) {
    cout << "[";
    for (const int& num : nums) {
        cout << num << ",";
    }
    cout << "]";
}

/*
    哈希表

    将所有的数放入哈希表，随后从 1 开始依次枚举正整数，判断其是否在哈希表中。 
    
    时间复杂度：O(n)
        其中 n 是数组的长度，遍历数组两次。
    空间复杂度：O(n)
*/
class Solution_0 {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int> hash;
        for (const auto& x : nums) {
            hash.insert(x);
        }
        int res = 1;
        while (hash.count(res)) {
            res ++;
        }

        return res;
    }
};

/*
    标记：
        对数组进行遍历，将不在 [1,N] 范围内的数修改成任意一个大于 N 的数。
        然后，将在 [1,N] 范围内的数修改为负数，即标记为负号。

    第一次遍历数组：
        将数组中所有小于等于 0 的数修改为 N+1。
    第二次遍历数组：
        若 x∈[1,N]，则给数组中的第 x−1 个位置的数添加一个负号。
        若它是负数，则不添加符号。
    第三次遍历数组：
        若数组中的每一个数都是负数，则答案是 N+1；
        否则，答案是第一个正数的位置加 1。

    时间复杂度：O(n)
        其中 n 是数组的长度，遍历数组三次。
    空间复杂度：O(1)
        没有使用额外的空间
*/
class Solution_1 {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int& x : nums) {
            if (x <= 0) {
                x = n + 1;
            }
        }
        for (int i = 0; i < n; i ++) {
            int x = abs(nums[i]);
            if (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;
    }
};

/*
    置换：
        将每个数字放到它在数组中的正确位置，数字 i 应该放在数组的索引 i-1 处。

    第一次遍历数组：
        将每个正数 nums[i] 放置到正确的位置 nums[nums[i]-1]，通过交换元素来实现。
    第二次遍历数组：
        找到第一个不满足 nums[i] != i+1 的位置 i，i+1 即为缺失的第一个正数。
    
    时间复杂度：O(n)
        其中 n 是数组的长度，遍历数组两次。
    空间复杂度：O(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[nums[i] - 1] != nums[i]) {
                swap(nums[nums[i] - 1], nums[i]);
            }
        }
        for (int i = 0; i < n; i ++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        return n + 1;
    }
};

int main() {
    Solution solution;
     vector<vector<int>> nums = { 
        {1,2,0},
        {3,4,-1,1},
        {7,8,9,11,12}
    };

    for (auto& num : nums) {
        cout << "Input: ";
        printArray(num);
        cout << endl;
        int result = solution.firstMissingPositive(num);
        cout << "Output: " << result << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   哈希表

   时间复杂度：O(n)
       其中 n 是数组的长度，遍历数组两次。
   空间复杂度：O(n)
*/
func firstMissingPositive_0(nums []int) int {
    // 创建一个哈希表
    hash := make(map[int]bool)
    // 将数组中的元素添加到哈希表中
    for _, num := range nums {
        hash[num] = true
    }
    // 从头开始遍历，找到第一个不在哈希表中的正数
    for i := 1; i <= len(nums); i ++ {
        if !hash[i] {
            return i
        }
    }

    return len(nums) + 1
}
/*
    1.遍历数组，将每个正数 nums[i] 放置到正确的位置上 nums[nums[i]-1]，通过交换元素来实现。
    2.再次遍历数组，找到第一个不满足 nums[i] == i+1 的位置 i。
        返回 i+1，即为缺失的第一个正数。
        若所有位置都满足条件，则返回数组长度加 1。
    
    时间复杂度：O(n)
        其中 n 是数组的长度，遍历数组两次。 
    空间复杂度：O(1)
        使用了固定的几个变量。
*/
func firstMissingPositive(nums []int) int {
    n := len(nums)
    for i := 0; i < n; i ++ {
        for nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i] {
            nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        }
    }
    for i := 0; i < n; i ++ {
        if nums[i] != i + 1 {
            return i + 1
        }
    }

    return n + 1
}

func main() {
    // 测试用例
    testCases := []struct {
        nums     []int
        expected int
    }{
        {[]int{1,2,0}, 3},
        {[]int{3,4,-1,1}, 2},
        {[]int{7,8,9,11,12}, 1},
    }
    
    for i, tc := range testCases {
        fmt.Printf("Test Case %d, Input: nums = %v\n", i+1, tc.nums)
		result := firstMissingPositive(tc.nums)

		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}