首页 > 编程笔记 > C语言笔记

C语言数组去重的3种方法（附带源码）

数组去重是一个常见的编程任务，但是C语言标准库并没有提供相关的函数，所以这个需要我们自己来实现。
 

在开始之前，我们需要明确什么是数组去重。数组去重是指从一个包含重复元素的数组中删除重复项，只保留每个元素的一个实例。例如，对于数组 {1, 2, 2, 3, 4, 4, 5}，去重后的结果应该是 {1, 2, 3, 4, 5}。


我们将探讨两种主要的去重方法（使用双重循环和使用排序后比较），以及一种补充的去重方法（使用哈希表）。这些方法各有优缺点，适用于不同的场景。

方法一：使用双重循环

这种方法的基本思路是遍历数组，对于每个元素，检查它是否在之前的元素中出现过。如果没有出现过，我们就将它保留在结果数组中。这种方法的优点是不需要额外的存储空间，缺点是时间复杂度较高，为 O(n^2)。
 

以下是具体的实现代码：

#include <stdio.h>

int removeDuplicates(int arr[], int n) {
    if (n == 0 || n == 1) {
        return n;
    }

    int j = 0;
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] != arr[i + 1]) {
            arr[j++] = arr[i];
        }
    }
    arr[j++] = arr[n - 1];

    return j;
}

int main() {
    int arr[] = {1, 2, 2, 3, 4, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    n = removeDuplicates(arr, n);

    printf("去重后的数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

在这个实现中，我们定义了一个 removeDuplicates 函数，它接受一个整型数组和数组长度作为参数。函数通过比较相邻元素来去除重复项，并返回新数组的长度。在 main 函数中，我们调用 removeDuplicates 函数并打印结果。

输出结果： 
去重后的数组：
1 2 3 4 5

方法二：使用排序后比较

这种方法首先对数组进行排序，然后比较相邻元素来去除重复项。这种方法的时间复杂度取决于排序算法，通常为 O(n log n)，空间复杂度为 O(1)（如果使用原地排序算法）。


以下是使用快速排序和去重的实现代码：

#include <stdio.h>

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int removeDuplicates(int arr[], int n) {
    if (n == 0 || n == 1) {
        return n;
    }

    quickSort(arr, 0, n - 1);

    int j = 0;
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] != arr[i + 1]) {
            arr[j++] = arr[i];
        }
    }
    arr[j++] = arr[n - 1];

    return j;
}

int main() {
    int arr[] = {4, 2, 1, 3, 4, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    n = removeDuplicates(arr, n);

    printf("去重后的数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

在这个实现中，我们首先定义了快速排序所需的辅助函数 swap 和 partition，以及主要的 quickSort 函数。然后，在 removeDuplicates 函数中，我们先对数组进行排序，再比较相邻元素来去除重复项。

输出结果： 
去重后的数组：
1 2 3 4 5

这两种方法各有优缺点。双重循环方法简单直观，适用于小规模数据，但对于大规模数据效率较低。排序后比较方法在处理大规模数据时效率更高，但需要改变原数组的顺序。
 

在实际应用中，我们还需要考虑其他因素，如是否需要保持原数组的顺序、是否允许修改原数组、内存使用限制等。根据具体需求，我们可能需要对这些基本方法进行调整或选择其他更适合的算法。

方法三：使用哈希表

除了上述两种方法，还有一些其他的去重技巧值得一提。例如，我们可以使用哈希表来实现 O(n) 时间复杂度的去重，但这需要额外的空间。在C语言中，可以使用数组模拟简单的哈希表，特别是当我们知道数组元素的范围时。
 

以下是使用数组模拟哈希表进行去重的示例代码：

#include <stdio.h>
#include <limits.h>

#define MAX_ELEMENT 1000  // 假设元素的最大值不超过 1000

int removeDuplicates(int arr[], int n) {
    int hash[MAX_ELEMENT + 1] = {0};  // 初始化哈希表
    int j = 0;

    for (int i = 0; i < n; i++) {
        if (hash[arr[i]] == 0) {
            arr[j++] = arr[i];
            hash[arr[i]] = 1;
        }
    }

    return j;
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6, 2, 9, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    n = removeDuplicates(arr, n);

    printf("去重后的数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

这种方法的时间复杂度为 O(n)，空间复杂度为 O(MAX_ELEMENT)。它的优点是速度快，并且保持了元素的原始顺序；缺点是需要额外的内存空间，且只适用于元素值在一定范围内的情况。

输出结果： 
去重后的数组：
5 2 9 1 6 7

总结起来，C语言中的数组去重是一个看似简单，但实际上涉及多种考虑因素的问题。我们需要根据具体的应用场景、数据规模、内存限制等因素来选择最合适的方法。

相关文章