去掉重复的数据C语言PTA

在C语言中，要去除数组或其他容器中的重复数据，通常需要结合一些数据结构和算法。这里可以介绍两种常见的方法：

1. **使用哈希表（Hash Table）**:
使用哈希表（如`std::unordered_set`或自定义实现）可以高效地去重。遍历输入数组，对于每个元素，检查它是否已经存在于哈希表中。如果不在，就添加到哈希表中；如果已存在，则表示重复。最后，将哈希表的元素复制回一个新的数组，得到的就是无重复的数据。

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

// 自定义哈希函数和桶数组
#define TABLE_SIZE 100
typedef int (*HashFunction)(const void*);

void removeDuplicates(int* arr, size_t n, HashFunction hashFunc) {
    bool used[TABLE_SIZE] = {false};
    for (size_t i = 0; i < n; ++i) {
        int val = hashFunc(&arr[i]);
        if (!used[val]) {
            printf("%d ", arr[i]); // 打印非重复元素
            used[val] = true;
        }
    }
}

int main() {
    int input[] = {1, 5, 3, 1, 7, 8, 3, 9, 5};
    size_t n = sizeof(input) / sizeof(input[0]);

    removeDuplicates(input, n, /* 你自己实现的哈希函数 */);
    return 0;
}

2. **排序后删除重复**:
如果允许对数组进行排序，可以在遍历过程中直接跳过相等的元素。这适用于数值型数组，因为比较容易确定重复项。

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

void removeDuplicates(int* arr, size_t n) {
    qsort(arr, n, sizeof(int), compare); // 对数组排序
    size_t i = 0;
    for (size_t j = 1; j < n; ++j) {
        if (arr[j] != arr[i]) {
            i++;
            arr[i] = arr[j]; // 移除重复并更新索引
        }
    }
    arr[i + 1] = 0; // 由于减少了一个元素，最后一个元素可能是多余的
}

int compare(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int main() {
    int input[] = {1, 5, 3, 1, 7, 8, 3, 9, 5};
    size_t n = sizeof(input) / sizeof(input[0]);

    removeDuplicates(input, n);

    // 现在数组 [1, 5, 3, 7, 8, 9] 就是没有重复项了
    for (size_t i = 0; input[i]; ++i)
        printf("%d ", input[i]);
    return 0;
}