在C语言中能否以O(N)时间结合辅助数据结构检测数组重复？

Hey there! Great question—let me start by confirming: yes, you can absolutely detect duplicate elements in an array with O(N) time complexity in C, and this holds true even when you account for the overhead of inserting elements into a hash table or similar auxiliary structure.

The magic here relies on hash-based data structures. A hash table (or hash set, since we only care about existence, not key-value pairs) has average-case O(1) time for both insertions and lookups. If we iterate through each element in the array once, and for each element we:

• Check if it's already present in the hash set
• If it is, we've found a duplicate—we can immediately return true
• If not, insert it into the set and move on

Since each of these operations is O(1) on average, doing this N times gives us an overall O(N) time complexity.

C's standard library doesn't include a built-in hash set, but we can easily implement a simple one ourselves. Let's go with a chained hash table (to handle hash collisions) as an example:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Define a node for the chained hash table
typedef struct HashNode {
    int value;
    struct HashNode* next;
} HashNode;

// Define the hash set structure
typedef struct HashSet {
    HashNode** buckets;
    size_t size;
} HashSet;

// Simple hash function for integers
size_t hash(int value, size_t bucket_count) {
    // Adjust negative numbers to positive before modulo
    return (size_t)(value < 0 ? -value : value) % bucket_count;
}

// Initialize a hash set with a given number of buckets
HashSet* hash_set_init(size_t bucket_count) {
    HashSet* set = malloc(sizeof(HashSet));
    set->buckets = calloc(bucket_count, sizeof(HashNode*));
    set->size = bucket_count;
    return set;
}

// Check if a value exists in the hash set
bool hash_set_contains(HashSet* set, int value) {
    size_t index = hash(value, set->size);
    HashNode* current = set->buckets[index];
    while (current != NULL) {
        if (current->value == value) {
            return true;
        }
        current = current->next;
    }
    return false;
}

// Insert a value into the hash set (returns false if already exists)
bool hash_set_insert(HashSet* set, int value) {
    if (hash_set_contains(set, value)) {
        return false;
    }
    size_t index = hash(value, set->size);
    HashNode* new_node = malloc(sizeof(HashNode));
    new_node->value = value;
    new_node->next = set->buckets[index];
    set->buckets[index] = new_node;
    return true;
}

// Free the hash set to avoid memory leaks
void hash_set_free(HashSet* set) {
    for (size_t i = 0; i < set->size; i++) {
        HashNode* current = set->buckets[i];
        while (current != NULL) {
            HashNode* temp = current;
            current = current->next;
            free(temp);
        }
    }
    free(set->buckets);
    free(set);
}

// Function to detect duplicates in an array
bool has_duplicates(int* arr, size_t arr_size) {
    // Use 2x array size for buckets to reduce collision chance
    HashSet* set = hash_set_init(arr_size * 2);
    bool result = false;

    for (size_t i = 0; i < arr_size; i++) {
        if (!hash_set_insert(set, arr[i])) {
            result = true;
            break;
        }
    }

    hash_set_free(set);
    return result;
}

// Example usage
int main() {
    int arr1[] = {1, 2, 3, 4, 5};
    int arr2[] = {1, 3, 2, 4, 3};

    printf("Array 1 has duplicates: %s\n", has_duplicates(arr1, 5) ? "Yes" : "No");
    printf("Array 2 has duplicates: %s\n", has_duplicates(arr2, 5) ? "Yes" : "No");

    return 0;
}

• Average Case: This runs in O(N) time. Each insertion and lookup is O(1) on average because hash collisions are rare when using a good hash function and enough buckets.
• Worst Case: In the extremely unlikely scenario where every element has the same hash value (full collisions), this degrades to O(N²) time. But with a well-chosen hash function and bucket count (like 2x the array size), this case is practically avoidable.
• Alternative for Limited Value Ranges: If your array elements are integers within a known, small range (e.g., 0 to 1000), you can use a simple boolean array as a "hash set". This gives you strict O(N) time with no collision overhead—just mark an index as true when you encounter the value, and check if it's already true before marking.

Yes, O(N) time is totally achievable in C for duplicate detection using hash-based structures. The key is leveraging the average O(1) operations of hash tables to keep the overall complexity linear.

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