如何以O(n)时间复杂度寻找给定数组中缺失的最小正整数？

Absolutely feasible! This is a classic problem that can definitely be solved in O(n) time (and even O(1) extra space if you're allowed to modify the input array). Let me walk you through the approach step by step, using your example to make it tangible.

Core Insight #

For an array of length n, the smallest missing positive integer must lie in the range [1, n+1]. Here's why:

• If all integers from 1 to n are present in the array, the smallest missing positive is n+1.
• If any integer in 1 to n is missing, that's our answer.

In-Place Swapping Method (O(n) time, O(1) space) #

The idea is to rearrange the array so that each positive integer x (where 1 ≤ x ≤ n) is placed at the index x-1. Once we've done this, we can simply scan the array to find the first index where the value doesn't match index + 1—that's our missing number.

Let's apply this to your example: [-3,-6,1,-9,4,6,0] (length n=7):

1. First pass: Rearrange elements
   • Skip numbers that are ≤0 or >7 (they can't be part of the 1~7 range we care about).
   • For valid numbers, swap them to their correct positions:
     • The 1 at index 2 gets swapped to index 0 → array becomes [1,-6,-3,-9,4,6,0].
     • The 4 at index 4 gets swapped to index 3 → array becomes [1,-6,-3,4,-9,6,0].
     • The 6 at index 5 is already at its correct position (index 5 = 6-1), so we leave it.
2. Second pass: Find the missing number
   • Scan each index:
     • Index 0: value is 1 (matches 0+1 → correct).
     • Index 1: value is -6 (doesn't match 1+1=2 → this is our missing number!).

Code Example (Python) #

def find_smallest_missing_positive(nums):
    n = len(nums)
    for i in range(n):
        # Keep swapping until the current element is in the right place or invalid
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            # Swap nums[i] with the element at its target position
            target_idx = nums[i] - 1
            nums[i], nums[target_idx] = nums[target_idx], nums[i]
    
    # Check for the first mismatched index
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    # If all 1..n are present, return n+1
    return n + 1

# Test with your example
test_array = [-3,-6,1,-9,4,6,0]
print(find_smallest_missing_positive(test_array))  # Output: 2

Why is this O(n) time? #

Even though there's a nested while loop, each element is swapped to its correct position at most once. Once an element is in the right spot, we never touch it again. This means the total number of swap operations is O(n), making the overall time complexity linear.

If you can't modify the input array, you can also use a hash set to store all positive integers from the array, then check from 1 upwards until you find a number not in the set. This is still O(n) time but uses O(n) extra space.

Hope this makes the solution clear!

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