题目

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

示例：

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

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

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

解答 & 代码

解法一：原地哈希

将给定的数组设置为哈希表的替代品。
对于长为 len 的数组，缺失的的最小正整数只能在 [1, len+1] 中（如果数组包含 [1, len] 的所有正整数，缺失的最小正整数就是 len+1，否则是 [1, len] 中未出现的最小正整数）
因此，我们希望数组相当于一个哈希表，每个位置 **i** 的元素能表示正整数 **i+1** 是否存在

首先，遍历数组的每个元素，如果该元素的值小于等于 0，就将其修改为 len + 1
- 遍历结束后，数组中元素都为正数
其次，遍历数组的每个元素 nums[i]，如果 nums[i] 的绝对值 ∈ [1, len]，则将数组中下标为 nums[i] - 1 的元素加上负号（若已经为负数则不变）
- 遍历结束后，对于数组中的每个下标 **i**，若 nums[i] 为正数，代表不存在正整数 **i+1**；若 **nums[i]** 为负数，代表存在正整数 **i+1**

最后，遍历数组的每个元素 nums[i]，如果 nums[i] 是正数，说明不存在正整数 i + 1，返回 i + 1

遍历结束，若所有元素都为负数，说明存在 [1, len] 的每个正整数，因此返回 len + 1

class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
   int len = nums.size();
   // 1. 遍历数组，将数组中小于等于 0 的元素都修改为 len+1，使得数组中所有元素都为正数
   for(int i = 0; i < len; ++i)
   {
       if(nums[i] <= 0 || nums[i] > len)
           nums[i] = len + 1;
   }
   // 2. 遍历数组中的每个元素 nums[i]，
   // 如果其绝对值∈[1,len]，则将数组中下标为 nums[i]-1 的元素加上负号，变为负数（若已为负数则不变）
   for(int i = 0; i < len; ++i)
   {
       int num = nums[i] > 0 ? nums[i] : -nums[i];    // 取当前元素的绝对值
       if(num > 0 && num <= len)
           nums[num - 1] = nums[num - 1] > 0 ? -nums[num - 1] : nums[num - 1];
   }
   // 3. 遍历数组中的每个元素，如果某个位置 i 的元素是正数（即未被标记）
   // 说明数组中不存在 i+1，返回 i+1
   for(int i = 0; i < len; ++i)
   {
       if(nums[i] > 0)
           return i + 1;
   }
   // 若数组中所有位置的元素都为负数（都被标记），说明数组中包含 [1,len] 的每个正整数
   // 因此返回 len+1
   return len + 1;
}
};

执行结果： ``` 执行结果：通过

执行用时：156 ms, 在所有 C++ 提交中击败了 11.78% 的用户内存消耗：80.8 MB, 在所有 C++ 提交中击败了 11.34% 的用户

<a name="EZ55D"></a>
## 解法二：置换
想法：将数组恢复成如下格式：

- **如果数组中包含 **`**x∈[1, len]**`**，那么恢复后的数组的第 **`**x-1**`** 个元素为 **`**x**` 

做法：

- 遍历数组的每个元素 `nums[i]`，如果 `nums[i]∈[1, len]`，就将 `nums[i]` 和第 `nums[i] - 1` 个元素 `nums[nums[i] - 1]` 交换（如果 `nums[i]` 和 `nums[nums[i] - 1]` 相等，则不交换，否则陷入死循环）。交换完成后，如果新的 `nums[i]∈[1, len]`，则继续交换
- 恢复后，遍历数组，如果位置 `i` 的元素不是 `i+1`，那么说明缺失的最小正数就是 `i+1`，返回
```cpp
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int len = nums.size();
        // 遍历数组，恢复数组到如下形式：
        // 如果数组中包含 x∈[1, len]，那么恢复后的数组的第 x-1 个元素为 x 
        for(int i = 0; i < len; ++i)
        {
            while(nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i])
                swap(nums[i], nums[nums[i] - 1]);
        }
        // 恢复数组后，遍历数组，如果位置 i 的元素不是 i+1，那么说明缺失的最小正数就是 i+1，返回
        for(int i = 0; i < len; ++i)
        {
            if(nums[i] != i + 1)
                return i + 1;
        }
        return len + 1;
    }
};

执行结果：

执行结果：通过

执行用时：124 ms, 在所有 C++ 提交中击败了 37.44% 的用户
内存消耗：80.9 MB, 在所有 C++ 提交中击败了 10.02% 的用户

CodeTop 企业题库

[困难] 41. 缺失的第一个正数

题目

解答 & 代码

解法一：原地哈希