力扣41. 缺失的第一个正数（困难）

思路

寻找缺失的第一个正数，但是要求时间复杂度O(n)、空间复杂度O(1)，这说明我们不能使用排序算法，也不能使用哈希表来存放数组元素，我们可以使用原地置换的方法。

方法

假设我们数组长度是n，里面是打乱的1 - n的数字，排序后应该是1, 2, 3, ..., n（1对应索引0， n对应索引n - 1），现在数组里缺少了一个正整数，多了一个小于等于0或者大于n的数字。

我们有如下思路：

1. 我们遍历一遍数组，如果第i个位置的元素大于0，小于等于n，并且这个位置的元素不在正确位置（即第i个位置的元素不是i + 1），我们就把第i个位置的元素交换到其对应位置，此时我们这个位置的元素就是从原先i的正确位置上交换过来的元素，我们重复这个过程，让当前元素全部放至指定位置，可以用while循环完成这个操作，当while循环结束的时候，说明我们当前位置的元素是i + 1或者小于等于0或者大于n，我们不断往下遍历，当遍历结束的时候，我们的排序也已完成，时间复杂度为O(n)。

有人说这样做最坏情况下复杂度不止O(n)，实际上，对于数组中的每个元素，最多只会被交换2次，第一次是把这个元素从别处交换过来，第二次是放至指定位置。

2. 我们再遍历一遍数组，这次遍历数组是查看对应位置i的元素是否是我们的指定元素i + 1，如果不是i + 1，说明i + 1这个元素在数组中不存在，直接返回i + 1。

3. 如果遍历结束没有返回（即所有元素都在指定位置），我们就返回（n + 1），即数组大小 + 1，因为1 - n都存在于数组，最小正数是n + 1。

复杂度

• 时间复杂度: O(N)

• 空间复杂度: O(1)

代码

下方为力扣提交代码，可以查看我的题解41. 缺失的第一个正数 - 力扣（LeetCode）

class Solution {
public:
	//用于数组元素交换的函数
	void swap(int *a, int *b) {
		int tmp = *a;
		*a = *b;
		*b = tmp;
	}	
	
    int firstMissingPositive(vector<int>& nums) {
		//第一次遍历，所有元素放置至指定位置
		for (int i = 0; i < nums.size(); i++) {
			while (nums[i] > 0 && nums[i] <= nums.size() && nums[i] != nums[nums[i] - 1]) {
				swap(&nums[i], &nums[nums[i] - 1]);
			}	
		}
		//第二次遍历，寻找缺失的第一个正数
		for (int i = 0; i < nums.size(); i++) {
			if (nums[i] != i + 1) {
				return i + 1;
			}
		}
		//如果所有元素都在指定位置，返回（数组大小 + 1）
		return nums.size() + 1;
    }
};

下方为测试代码，ACM格式，包括头函数、主函数等。

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

class Solution {
public:
	void swap(int *a, int *b) {
		int tmp = *a;
		*a = *b;
		*b = tmp;
	}	
	
    int firstMissingPositive(vector<int>& nums) {
		for (int i = 0; i < nums.size(); i++) {
			while (nums[i] > 0 && nums[i] <= nums.size() && nums[i] != nums[nums[i] - 1]) {
				swap(&nums[i], &nums[nums[i] - 1]);
			}	
		}
		for (int i = 0; i < nums.size(); i++) {
			if (nums[i] != i + 1) {
				return i + 1;
			}
		}
		return nums.size() + 1;
    }
};

int main() {
	vector<int> nums = {3, 4, -1, 1};
	Solution s;
	int result = s.firstMissingPositive(nums);
	cout << result << endl;
}

输出样例

2