C++：不排序去除vector重复值，解决缺失正整数代码失效问题

Hey there! I totally get your frustration—duplicates in your vector are breaking your FirstMissingPositive function, and you can't sort the array because your logic relies on the original order. Let's fix this with an efficient solution that sticks to your constraints: O(N) worst-case time and O(N) worst-case space (excluding input storage).

The Core Idea: Use a Hash Set for O(1) Duplicate Checks #

Since we can't sort, the fastest way to track duplicates is with an unordered set (C++'s unordered_set), which gives average O(1) insertions and lookups (worst-case O(N), but overall still fits your time requirement). This lets us filter out duplicates without altering the original vector's order.

Solution 1: Extract Unique Positives First, Then Find the Missing One #

This approach first collects all unique positive integers from the vector, then checks sequentially from 1 upwards to find the first missing value. It's straightforward and preserves the original array entirely:

#include <vector>
#include <unordered_set>

int FirstMissingPositive(std::vector<int>& nums) {
    std::unordered_set<int> unique_positives;
    int max_pos = 0;

    // Step 1: Gather all unique positive numbers and track the largest one
    for (int num : nums) {
        if (num > 0) {
            unique_positives.insert(num);
            if (num > max_pos) {
                max_pos = num;
            }
        }
    }

    // Step 2: Check from 1 to max_pos for the first missing positive
    for (int i = 1; i <= max_pos; ++i) {
        if (unique_positives.find(i) == unique_positives.end()) {
            return i;
        }
    }

    // If all numbers from 1 to max_pos exist, return the next integer
    return max_pos + 1;
}

Solution 2: Integrate Duplicate Checks Into Your Existing Logic #

If you need to keep your original processing flow (e.g., you're doing in-place swaps like the classic first missing positive algorithm), you can use a set to track already processed values and skip duplicates to avoid infinite loops or incorrect state:

#include <vector>
#include <unordered_set>

int FirstMissingPositive(std::vector<int>& nums) {
    std::unordered_set<int> processed;
    int n = nums.size();

    for (int i = 0; i < n; ++i) {
        int current = nums[i];
        // Skip non-positives, out-of-range values, or duplicates we've already handled
        if (current <= 0 || current > n || processed.count(current)) {
            continue;
        }

        processed.insert(current);
        // Your original in-place swap logic (adjust if your code differs)
        while (current > 0 && current <= n && nums[current - 1] != current) {
            std::swap(nums[i], nums[current - 1]);
            current = nums[i]; // Update current after swap
            // Break early if we hit a duplicate we've already processed
            if (processed.count(current)) {
                break;
            }
            processed.insert(current);
        }
    }

    // Find the first position where the value doesn't match the index + 1
    for (int i = 0; i < n; ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }

    return n + 1;
}

Why This Works #

• Time Complexity: Each element is processed at most twice (once in the initial loop, once in the swap loop), so overall O(N). Set operations are average O(1), worst-case O(N) but still keeps the total time linear.
• Space Complexity: The set stores up to N unique positive integers, so O(N) space, which meets your requirement.
• Order Preservation: Neither solution sorts the original vector, so your order-dependent logic remains intact.

内容的提问来源于stack exchange，提问作者arcoxia tom