在O(N)时间复杂度与O(1)额外空间复杂度下判断数组元素是否唯一——是否可行？

Great question—this cuts to the heart of what's possible when working with constrained time and space, especially when dealing with unbounded values. Let's break this down step by step.

First, Let's Clarify the Problem #

Given an array of length n containing 32-bit ints (with no upper/lower bound on values), determine if any duplicate elements exist. The solution must run in O(n) time, use O(1) extra space (we can modify the original array), and cannot use a hash table represented by a giant 2^(2^32)-bit variable.

What We Know About Constrained Cases #

We already have a working solution when elements are limited to the range [0, n-1]:

• Iterate through each element num in the array.
• For each num, check the value at index abs(num). If it's negative, we've found a duplicate (since we marked it earlier).
• If it's positive, flip it to negative to mark that we've seen abs(num).

This works because every element maps directly to a valid index in the array, letting us use the array itself as a space-efficient "hash table" without extra memory. But this relies entirely on the range constraint—remove that, and the approach falls apart.

Why the Unbounded Case Is Impossible to Solve #

Without the [0, n-1] range constraint, elements can be any 32-bit integer—most of which won't correspond to a valid index in the array (since n can be much smaller than 2^31-1). Here's why no solution can exist under the given constraints:

1. Information Theory Argument #

Each 32-bit int has 2^32 possible values. For an array of length n, there are (2^32)^n possible input arrays. To distinguish between arrays with duplicates and those without, we need to track which values we've seen.

But O(1) extra space means we have a fixed, constant number of bits to store state—no matter how large n gets. As n grows beyond the number of bits we can use, we can't possibly remember all the distinct values we've encountered. There are simply too many possible values to track with a fixed amount of memory.

2. Concrete Counterexample #

Consider two arrays:

• Array A: Contains n distinct values, all larger than n-1 (e.g., n, n+1, ..., 2n-1).
• Array B: Identical to Array A, but the last element is replaced with n (creating a duplicate).

Any O(1) space algorithm can't tell these arrays apart. Since all elements are outside the array's index range, we can't use the array itself to mark seen values. With fixed memory, we can't store all n distinct values from Array A—so when we reach the last element of Array B, we have no way of knowing we've already seen n. The algorithm would either incorrectly flag Array A as having duplicates, or miss the duplicate in Array B.

3. Reductio ad Absurdum #

If we could solve this problem, we'd be able to store n distinct integers in O(1) space—which is impossible. The amount of information needed to distinguish between all possible sets of n distinct integers grows with n, but O(1) space gives us a fixed amount of memory regardless of n.

Final Verdict #

There is no solution to this problem under the given constraints. The key barrier is the lack of a range constraint tying array elements to valid indices—without that, we can't leverage the array itself to track seen values, and O(1) space is insufficient to remember arbitrary integers as n scales.

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