C语言编程题查找数组中的重复元素

1、暴力法

最简单的方法，使用两层嵌套循环来检查每对元素是否相同。时间复杂度为O(n^2)，不推荐在大型数组上使用，因为效率较低。

#include <stdio.h>

void findDuplicatesBruteForce(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            if (arr[i] == arr[j]) {
                printf("Duplicate found: %d\n", arr[i]);
            }
        }
    }
}

int main() {
    int arr[] = {4, 3, 2, 7, 8, 2, 3, 1}; // 示例数组
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Using Brute Force:\n");
    findDuplicatesBruteForce(arr, size);

    return 0;
}

2、使用哈希表

利用哈希表（散列表）来存储每个元素及其出现次数，时间复杂度为O(n)，但需要额外的空间来存储哈希表。

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

#define MAX_SIZE 100 // 假设数组的最大大小为100

void findDuplicatesUsingHash(int arr[], int size) {
    int hash[MAX_SIZE] = {0}; // MAX_SIZE 应足够大

    for (int i = 0; i < size; i++) {
        hash[arr[i]]++;
    }

    for (int i = 0; i < MAX_SIZE; i++) {
        if (hash[i] > 1) {
            printf("Duplicate found: %d\n", i);
        }
    }
}

int main() {
    int arr[] = {4, 3, 2, 7, 8, 2, 3, 1}; // 示例数组
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Using Hash Table:\n");
    findDuplicatesUsingHash(arr, size);

    return 0;
}

3、排序后查找

先对数组进行排序，然后检查相邻的元素是否相同。时间复杂度为O(n log n)，空间复杂度取决于排序算法的实现。

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

// Helper comparison function for sorting
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}


// Function to find duplicates in an array using sorting
void findDuplicatesSorting(int arr[], int size) {
    qsort(arr, size, sizeof(int), compare);

    for (int i = 1; i < size; i++) {
        if (arr[i] == arr[i - 1]) {
            printf("Duplicate found: %d\n", arr[i]);
        }
    }
}


int main() {
    int arr[] = {4, 3, 2, 7, 8, 2, 3, 1}; // Example array
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Using Sorting:\n");
    findDuplicatesSorting(arr, size);

    return 0;
}

4、使用标记数组

如果数组中的元素在一定范围内（例如0到n-1），可以使用一个额外的标记数组来标记每个元素是否已经访问过。时间复杂度为O(n)，空间复杂度为O(n)。

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

void findDuplicatesUsingMarker(int arr[], int size) {
    int visited[size];
    memset(visited, 0, sizeof(visited));

    for (int i = 0; i < size; i++) {
        if (visited[arr[i]]) {
            printf("Duplicate found: %d\n", arr[i]);
        } else {
            visited[arr[i]] = 1;
        }
    }
}

int main() {
    int arr[] = {4, 3, 2, 7, 8, 2, 3, 1}; // 示例数组
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Using Marker Array:\n");
    findDuplicatesUsingMarker(arr, size);

    return 0;
}

5、使用异或操作

如果数组中的元素有特定的范围和性质，可以利用异或操作来找出重复的元素。这种方法具有较高的空间效率，但需要数组元素有一定的限制条件。

#include <stdio.h>

void findDuplicatesUsingXOR(int arr[], int size) {
    int xor = 0;

    for (int i = 0; i < size; i++) {
        xor ^= arr[i];
    }

    for (int i = 1; i < size; i++) {
        xor ^= i;
    }

    printf("Duplicate found: %d\n", xor);
}

int main() {
    int arr[] = {4, 3, 2, 7, 8, 2, 3, 1}; // 示例数组
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Using XOR Method:\n");
    findDuplicatesUsingXOR(arr, size);

    return 0;
}