一. 簡介

前面文章學習了對該題目的兩種解題思路，文章如下：

力扣網C語言編程題：缺失的第一個正數-CSDN博客

但是前面的實現上在空間復雜度上沒有滿足要求。本文學習一種在空間復雜度上為 O(1)的思路。

二.?力扣網C語言編程題：缺失的第一個正數

題目：缺失的第一個正數

給你一個未排序的整數數組 nums ，請你找出其中沒有出現的最小的正整數。

請你實現時間復雜度為 O(n) 并且只使用常數級別額外空間的解決方案。

示例 1：
輸入：nums = [1,2,0]
輸出：3
解釋：范圍 [1,2] 中的數字都在數組中。

示例 2：
輸入：nums = [3,4,-1,1]
輸出：2
解釋：1 在數組中，但 2 沒有。

示例 3：
輸入：nums = [7,8,9,11,12]
輸出：1
解釋：最小的正數 1 沒有出現。

提示：
? ? 1 <= nums.length <= 105
? ? -231 <= nums[i] <= 231 - 1

解題思路三：

通過示例分析可知，缺失的一個最小正整數數的范圍為 0 < data <= (n+1)，這個分析結果很重要；

遍歷數組元素，將每個元素交換放在對應位置上，例如，將元素值為1的元素 放在nums[0]上，2放在nums[1]上，...以此類推，numsSize值放在 nums[numsSize-1]位置上（假如有 元素值為numsSize）。?

遍歷數組，如果 num[i] != (i+1)，則返回 (i+1)值，就是缺失的第一個正整數。如果在數組中找不到這樣的元素，則缺失的第一個正整數就是 (numsSize+1)；

C語言實現如下：

#include <stdio.h>int firstMissingPositive(int* nums, int numsSize) { if((nums == NULL) && (!numsSize)) {return -1;}int i = 0;//遍歷數組，將元素放到對應的位置上for(i = 0; i < numsSize; i++) {//nums[i]位置上值不是 iwhile((nums[i] > 0) && (nums[i] <= numsSize) && (nums[i] != nums[nums[i]-1])) {int tmp = nums[i];nums[i] = nums[tmp-1];nums[tmp-1] = tmp;}}//遍歷數組，找到第一個 nums[i] != i+1int data = 0;    for(i = 0; i < numsSize; i++) {if(nums[i] != (i+1)) {data = (i+1);return data;}}//如果在數組沒有找到 nums[i] != i+1,則最小正整數為(numsSize+1)data = numsSize+1;   return data;
}

可以看出，這個實現方法實現了空間復雜度為 O(1)。不過時間復雜度增加了為 O(n*n)；