在C语言中以低于O(n²)复杂度查找无序结构体数组中的重复元素

Alright, let's break down how to solve this problem step by step. We need to identify pairs of elements in the struct info array where different IDs have identical time, x, and y values. The given constraint (each ID's time field is ordered) can help optimize our solution, but we'll cover both a general efficient approach and a simpler sorted approach.

Problem Recap #

We're given this struct definition:

struct info{ int id; int time; int x; int y; };

And an example array:

struct info arr[] = {{2, 10, 30, 40}, {1, 10, 30, 40}, {1, 15, 45, 50}, {1, 20, 23, 37}};

Our goal is to find the pair (ID 1 and ID 2) since they share the same time=10, x=30, y=40.

Solution 1: Hash Table Mapping (Efficient, Average O(n) Time) #

This approach uses a hash table to group elements by their time+x+y combination, then checks each group for multiple distinct IDs. It's ideal for large datasets since hash operations are average O(1).

Implementation Code #

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

struct info {
    int id;
    int time;
    int x;
    int y;
};

// Hash table node to store IDs for a unique time/x/y combo
typedef struct HashNode {
    int time;
    int x;
    int y;
    int* ids;
    int id_count;
    struct HashNode* next;
} HashNode;

// Simple hash function to map time/x/y to a hash value (adjust for your use case if collisions are frequent)
unsigned int hash(int time, int x, int y) {
    return (unsigned int)(time * 1000000 + x * 1000 + y);
}

// Find existing node for a specific time/x/y combo
HashNode* find_hash_node(HashNode** table, int table_size, int time, int x, int y) {
    unsigned int idx = hash(time, x, y) % table_size;
    HashNode* curr = table[idx];
    while (curr != NULL) {
        if (curr->time == time && curr->x == x && curr->y == y) {
            return curr;
        }
        curr = curr->next;
    }
    return NULL;
}

// Add element to the hash table, skipping duplicate IDs in the same group
void add_to_hash(HashNode** table, int table_size, struct info elem) {
    HashNode* node = find_hash_node(table, table_size, elem.time, elem.x, elem.y);
    if (node == NULL) {
        // Create new node for this combo
        node = (HashNode*)malloc(sizeof(HashNode));
        node->time = elem.time;
        node->x = elem.x;
        node->y = elem.y;
        node->id_count = 1;
        node->ids = (int*)malloc(sizeof(int));
        node->ids[0] = elem.id;
        node->next = NULL;
        // Insert into hash table bucket
        unsigned int idx = hash(elem.time, elem.x, elem.y) % table_size;
        node->next = table[idx];
        table[idx] = node;
    } else {
        // Skip if ID already exists in the group
        int id_exists = 0;
        for (int i = 0; i < node->id_count; i++) {
            if (node->ids[i] == elem.id) {
                id_exists = 1;
                break;
            }
        }
        if (!id_exists) {
            // Add new ID to the group
            node->id_count++;
            node->ids = (int*)realloc(node->ids, sizeof(int) * node->id_count);
            node->ids[node->id_count - 1] = elem.id;
        }
    }
}

// Find and print all duplicate ID pairs
void find_duplicate_pairs(struct info* arr, int arr_len) {
    int table_size = arr_len * 2; // Reduce hash collisions
    HashNode** hash_table = (HashNode**)calloc(table_size, sizeof(HashNode*));

    // Populate hash table with all elements
    for (int i = 0; i < arr_len; i++) {
        add_to_hash(hash_table, table_size, arr[i]);
    }

    // Check each group for multiple distinct IDs
    printf("Duplicate ID pairs found:\n");
    for (int i = 0; i < table_size; i++) {
        HashNode* curr = hash_table[i];
        while (curr != NULL) {
            if (curr->id_count >= 2) {
                // Generate all unique ID pairs in the group
                for (int j = 0; j < curr->id_count; j++) {
                    for (int k = j + 1; k < curr->id_count; k++) {
                        printf("(%d, %d) | time=%d, x=%d, y=%d\n",
                               curr->ids[j], curr->ids[k], curr->time, curr->x, curr->y);
                    }
                }
            }
            curr = curr->next;
        }
    }

    // Clean up allocated memory
    for (int i = 0; i < table_size; i++) {
        HashNode* curr = hash_table[i];
        while (curr != NULL) {
            HashNode* temp = curr;
            curr = curr->next;
            free(temp->ids);
            free(temp);
        }
    }
    free(hash_table);
}

int main() {
    struct info arr[] = {
        {2, 10, 30, 40},
        {1, 10, 30, 40},
        {1, 15, 45, 50},
        {1, 20, 23, 37}
    };
    int arr_len = sizeof(arr) / sizeof(arr[0]);
    find_duplicate_pairs(arr, arr_len);
    return 0;
}

Example Output #

Duplicate ID pairs found:
(2, 1) | time=10, x=30, y=40

Solution 2: Sort & Traverse (Simpler, O(n log n) Time) #

If you prefer avoiding custom hash table implementations, sorting the array by time, x, and y then traversing to find matching groups is a straightforward alternative.

Implementation Code #

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

struct info {
    int id;
    int time;
    int x;
    int y;
};

// Comparison function for qsort (sorts by time -> x -> y -> id)
int compare_info(const void* a, const void* b) {
    struct info* elem_a = (struct info*)a;
    struct info* elem_b = (struct info*)b;
    if (elem_a->time != elem_b->time) return elem_a->time - elem_b->time;
    if (elem_a->x != elem_b->x) return elem_a->x - elem_b->x;
    if (elem_a->y != elem_b->y) return elem_a->y - elem_b->y;
    return elem_a->id - elem_b->id;
}

// Find duplicates via sorted array traversal
void find_duplicates_sort(struct info* arr, int arr_len) {
    qsort(arr, arr_len, sizeof(struct info), compare_info);
    
    printf("Duplicate ID pairs found:\n");
    for (int i = 0; i < arr_len; ) {
        int j = i + 1;
        // Traverse all elements matching current time/x/y
        while (j < arr_len && arr[j].time == arr[i].time && arr[j].x == arr[i].x && arr[j].y == arr[i].y) {
            if (arr[j].id != arr[i].id) {
                printf("(%d, %d) | time=%d, x=%d, y=%d\n", arr[i].id, arr[j].id, arr[i].time, arr[i].x, arr[i].y);
            }
            j++;
        }
        i = j; // Skip to next unique group
    }
}

int main() {
    struct info arr[] = {
        {2, 10, 30, 40},
        {1, 10, 30, 40},
        {1, 15, 45, 50},
        {1, 20, 23, 37}
    };
    int arr_len = sizeof(arr) / sizeof(arr[0]);
    find_duplicates_sort(arr, arr_len);
    return 0;
}

Example Output #

Duplicate ID pairs found:
(1, 2) | time=10, x=30, y=40

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