每日leetcode第0023天 0041. First Missing Positive

这道题目的代码虽然不多，但确实是考查时间空间的利用的好题目。

要求中，时间复杂度是n，空间复杂度是1。

如果我们将元素直接进行双重循环遍历，

时间复杂度是n^2，空间复杂度是1。

如果我们将元素放到别的地方，例如哈希表中，再进行查询，

时间复杂度是n，空间复杂度是n。

如果我们将元素排序，再进行检查，

时间复杂度是nlogn，空间复杂度是1。

那么我们怎么做呢？

我们需要将原有数组中的数字进行交换，每个数字交换到它下标一致的位置上。

交换完后要记得再检查这个位置上换来的数字需不需要再交换，如果是负数，或者很大的数，又或者是重复的数（也就是那个位置上已经有一个好的了），那么就退出小循环。

从左往右都换好位置后，我们从下标1开始一个个检查，如果检查到某个位置上没有该数字就输出。最后如果检查完长度对应的数字了，就输出长度+1。

这个解法的时间复杂度是n，空间复杂度是1。复合要求。