给一串数字，找出缺失的最小正数。限制了时间复杂度为 O（n），空间复杂度为 O（1）。

解法一 交换

参考这里-space-and-O(n)-time?orderBy=most_votes)。

如果没限制空间复杂度，我们可以这样想。用一个等大的数组去顺序保存这些数字。

比如说，数组 nums [ 3 4 -1 1 8]，它的大小是 5。然后再创建一个等大的数组 a，初始化为 [ - 1，- 1，- 1，- 1，-1] 。然后我们遍历 nums，把数字分别存到对应的位置。1 就存到数组 a 的第 1 个位置（a [ 0 ]），2 就存到数组 a 的第 2 个位置（a [ 1 ]），3 就存到数组 a 的第 3 个位置（a [ 2 ]）...

nums [ 0 ] 等于 3，更新 a [ - 1，- 1，3，- 1，-1] 。

nums [ 1 ] 等于 4，更新 a [ - 1，- 1，3，4，-1 ] 。

nums [ 2 ] 等于 - 1，不是正数，忽略。

nums [ 3 ] 等于 1，更新 a [ 1，- 1，3，4，-1 ] 。

nums [ 4 ] 等于 8，我们的 a 数组只能存 1 到 5，所以同样忽略。

最后，我们只需要遍历 a 数组，遇到第一次 a [ i ] ！= i + 1，就说明缺失了 i + 1。因为我们的 a 数组每个位置都存着比下标大 1 的数。

当然，上边都是基于有一个额外空间讲的。如果没有额外空间，怎么办呢？

我们直接把原数组当成 a 数组去用。 这样的话，会出现的问题就是之前的数就会被覆盖掉。覆盖之前我们把它放回到当前数字的位置， 换句话说就是交换一下位置。然后把交换回来的数字放到应该在的位置，又交换回来的新数字继续判断，直到交换回来的数字小于 0，或者大于了数组的大小，或者它就是当前位置放的数字了。接着遍历 nums 的下一个数。具体看一下。

nums = [ 3 4 -1 1 8 ]

nums [ 0 ] 等于 3，把 3 放到第 3 个位置，并且把之前第 3 个位置的 -1 放回来，更新 nums [ -1， 4， 3， 1， 8 ]。

然后继续判断交换回来的数字，nums [ 0 ] 等于 -1，不是正数，忽略。

nums [ 1 ] 等于 4，把 4 放到第 4 个位置，并且把之前第 4个位置的 1 放回来，更新 nums [ -1， 1， 3， 4， 8 ]。

然后继续判断交换回来的数字，nums [ 1 ] 等于 1，把 1 放到第 1 个位置，并且把之前第 1 个位置的 -1 放回来，更新 nums [ 1， -1， 3， 4， 8 ]。

然后继续判断交换回来的数字，nums [ 1 ] 等于 -1，不是正数，忽略。

nums [ 2 ] 等于 3，刚好在第 3 个位置，不用管。

nums [ 3 ] 等于 4，刚好在第 4 个位置，不用管。

nums [ 4 ] 等于 8，我们的 nums 数组只能存 1 到 5，所以同样忽略。

最后，我们只需要遍历 nums 数组，遇到第一次 nums [ i ] ！= i + 1，就说明缺失了 i + 1。因为我们的 nums 数组每个位置都存着比下标大 1 的数。

看下代码吧，一个 for 循环，里边再 while 循环

publicintfirstMissingPositive(int[] nums) {
intn=nums.length;
//遍历每个数字for (inti=0; i<n; i++) {
//判断交换回来的数字while (nums[i] >0&&nums[i] <=n&&nums[i] !=nums[nums[i] -1]) {
//第 nums[i] 个位置的下标是 nums[i] - 1swap(nums, i, nums[i] -1);
        }
    }
//找出第一个 nums[i] != i + 1 的位置for (inti=0; i<n; i++) {
if (nums[i] !=i+1) {
returni+1;
        }
    }
//如果之前的数都满足就返回 n + 1returnn+1;
}
privatevoidswap(int[] nums, inti, intj) {
inttemp=nums[i];
nums[i] =nums[j];
nums[j] =temp;
}

时间复杂度：for 循环里边套了个 while 循环，如果粗略的讲，那时间复杂度就是 O（n²）了。我们再从算法的逻辑上分析一下。因为每交换一次，就有一个数字放到了应该在的位置，只有 n 个数字，所以 while 里边的交换函数，最多执行 n 次。所以时间复杂度更精确的说，应该是 O（n）。

空间复杂度：O（1）。

总

对于这种要求空间复杂度的，我们可以先考虑如果有一个等大的空间，我们可以怎么做。然后再考虑如果直接用原数组怎么做，主要是要保证数组的信息不要丢失。目前遇到的，主要有两种方法就是交换和取相反数。