leetcode41.缺失的第一个正数

Posted on | In |
Words count in article: 197 | Reading time ≈ 1

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例：

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

分析：

1
核心思想：把数字放到该放的位置

代码

  • C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        if (!n) return 1;

        for (auto& x : nums)
            if (x != INT_MIN) x --;

        for (int i = 0;i < n;i ++) {
            while ((nums[i] >= 0 && nums[i] < n) && nums[i] != i && nums[i] != nums[nums[i]])
                swap(nums[i], nums[nums[i]]);
        }

        for (int i = 0;i < n;i ++)
            if (nums[i] != i) return i + 1;

        return n + 1;
    }
};

[原题链接](41. 缺失的第一个正数 - 力扣（Leetcode）)

0%