如何将数组唯一元素检查的时间复杂度从O(n²)优化至O(nlogn)及以下？

Hey there! Let's break down how to optimize your duplicate check from O(n²) to something way more efficient. I'll walk you through both the O(nlogn) approach and an even faster O(n) method, with code examples to make it concrete.

The core idea here is that sorting groups duplicate elements next to each other, so we only need a single pass to spot duplicates. Sorting typically takes O(nlogn) time, and the subsequent linear scan is O(n)—so the overall time complexity is dominated by the sort, landing us at O(nlogn).

Here's a Python example:

def has_duplicates(arr):
    if len(arr) <= 1:
        return False
    # Perform in-place sort to save space (O(logn) auxiliary space for most built-in sorts)
    arr.sort()
    # Check each pair of adjacent elements
    for i in range(len(arr) - 1):
        if arr[i] == arr[i + 1]:
            return True
    return False

If you can't modify the original array, use sorted(arr) instead (this creates a copy, adding O(n) space overhead, but time complexity stays O(nlogn)).

If you're okay with trading a bit of space for speed, a hash set lets us check for duplicates in linear time. Hash set lookups and insertions are average O(1), so we can traverse the array once, tracking elements we've already seen.

Python example:

def has_duplicates(arr):
    seen = set()
    for element in arr:
        if element in seen:
            # Found a duplicate
            return True
        seen.add(element)
    # No duplicates found
    return False

This runs in O(n) average time, with O(n) space to store the set. It's the fastest approach for most cases, unless memory is extremely constrained (then the O(nlogn) sort-based method is better, as it uses minimal extra space).

Just to recap: the typical O(n²) method uses nested loops, where each element is compared to every other element. That's n*(n-1)/2 comparisons total—great for small arrays, but it gets exponentially slower as the array grows (e.g., an array of 10,000 elements would require ~50 million comparisons!).

内容的提问来源于stack exchange，提问作者b.x