Leetcode 41. 缺失的第一个正数

原题链接：Leetcode 41. First Missing Positive

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1:

Input: nums = [1,2,0]
Output: 3
1
2

Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
1
2

Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
1
2

Explanation: The smallest positive integer 1 is missing.

Constraints:

• 1 <= nums.length <= 10⁵
  -2³¹ <= nums[i] <= 2³¹ - 1

---

题目大意：

有一个长度为n的整数数组nums，要求返回没有在nums中出现的最小正数

思路：原地修改数组

首先想到的暴力做法就是哈希表，但是题目中要求 O(1) 的空间复杂度，那么考虑原地修改数组。原地修改数组的思想就是通过下标做标记。如果元素t出现过，就在对应下标t-1上做标记。

nums中的数可以分为：

• 负数和0，将他们映射为n+1
• 正数，将他们映射为相反数

那么打完标记后再遍历一次，遇到的第一个正数的下标就是所要答案，如果遍历完就返回n+1

C++代码：

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        // 将非正数都变为n+1
        for(int i = 0; i < n; i++ ){
            if(nums[i] <= 0)
                nums[i] = n+1;
        }

        // 对于小于n的元素, 存在就将其变为负数
        // 由于可能多次出现, 已经变为负数, 需要取绝对值进行处理
        for (int i = 0; i < n; ++i) {
            if (abs(nums[i]) <= n) {
                nums[abs(nums[i]) - 1] = -abs(nums[abs(nums[i]) - 1]);
            }
        }

        for(int i = 0; i < n; i++ ){
            if(nums[i] > 0)
                return i + 1;
        }
        return n + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)