41.first-missing-positive

Statement

简体中文English

Metadata

• Link: 缺失的第一个正数
• Difficulty: Hard
• Tag: 数组 哈希表

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

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

• 1 <= nums.length <= 5 * 105
• -231 <= nums[i] <= 231 - 1

Metadata

• Link: First Missing Positive
• Difficulty: Hard
• Tag: Array Hash Table

Given an unsorted integer array nums, return the smallest missing positive integer.

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

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

• 1 <= nums.length <= 5 * 105
• -231 <= nums[i] <= 231 - 1

Solution

C++

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

class Solution {
public:
    int firstMissingPositive(vector<int> &nums) {
        int n = nums.size();
        nums.push_back(INT_MAX);

        for (auto &c : nums) {
            if (c <= 0) {
                c = INT_MAX;
            }
        }

        for (auto &c : nums) {
            if (abs(c) <= n && nums[abs(c)] > 0) {
                nums[abs(c)] *= -1;
            }
        }

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

        return n + 1;
    }
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif

---

最后更新: October 11, 2023