LeetCode 41 缺失的第一个正数（C语言 原地哈希法）

LeetCode 41 缺失的第一个正数（C语言 原地哈希法）

题目：

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

示例1：

输入：nums = [1,2,0]
输出：3

示例2：

输入：nums = [3,4,-1,1]
输出：2

示例3：

输入：nums = [7,8,9,11,12]
输出：1

提示：

1 < = n u m s . l e n g t h < = 5 ∗ 1 0 5 1 <= nums.length <= 5 * 10^5 1<=nums.length<=5∗105
- 2 31 < = n u m s [ i ] < = 2 31 − 1 2^{31} <= nums[i] <= 2^{31} - 1 231<=nums[i]<=231−1

解题代码：

void swap(int *x, int *y){
    int temp = *x;
    *x = *y;
    *y = temp;
}

int firstMissingPositive(int* nums, int numsSize){
    // 遍历每一个位置
    for(int i = 0; i < numsSize; i++)
        // 找到每一个位置上对应的元素 假如给的数组大小为4 那么数组对应的元素排列应为[1, 2, 3, 4]
        // nums[i] = i + 1 下面这个while循环就是找到i位置上对应的元素
        while(nums[i] > 0 && nums[i] < numsSize && nums[nums[i] - 1] != nums[i])
            swap(&nums[i], &nums[nums[i] - 1]);
    // 找到没有出现的最小正整数
    for(int i = 0; i < numsSize; i++)
        if(nums[i] != (i+1))
            return i+1;
    // 全符合要求的情况下    
    return numsSize+1;
}