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

c语言去掉数组中重复的元素（3种方法）

在C语言编程中，去掉数组中重复的元素是一个常见的任务。这个操作可以帮助我们优化数据结构，减少内存使用，并且在某些算法中起到关键作用。本文将详细介绍如何在C语言中实现这一功能，并提供多种方法供读者选择。

方法一：使用双重循环

最直接的方法是使用双重循环来比较数组中的每个元素。这种方法简单易懂，适合初学者理解数组操作的基本原理。

#include <stdio.h>

void removeDuplicates(int arr[], int *size) {
    int i, j, k;
    for (i = 0; i < *size; i++) {
        for (j = i + 1; j < *size;) {
            if (arr[i] == arr[j]) {
                for (k = j; k < *size - 1; k++) {
                    arr[k] = arr[k + 1];
                }
                (*size)--;
            } else {
                j++;
            }
        }
    }
}

int main() {
    int arr[] = {1, 2, 2, 3, 4, 4, 5, 5, 6};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    removeDuplicates(arr, &size);
    
    printf("去重后的数组: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

这段代码中，我们定义了一个 removeDuplicates 函数，它使用双重循环来比较数组中的元素。外层循环遍历数组中的每个元素，内层循环则从当前元素的下一个位置开始，查找是否有重复元素。如果找到重复元素，我们就将后面的所有元素向前移动一位，effectively 删除了重复的元素。
 

这种方法的时间复杂度为 O(n²)，其中 n 是数组的长度。对于小型数组，这种方法简单有效，但对于大型数组可能会导致性能问题。

方法二：排序后去重

另一种更高效的方法是先对数组进行排序，然后再去除重复元素。这种方法的时间复杂度取决于所使用的排序算法，但通常可以达到 O(n log n)。

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

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

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

    qsort(arr, n, sizeof(int), compare);

    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[] = {5, 2, 8, 2, 3, 5, 1, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    n = removeDuplicates(arr, n);

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

    return 0;
}

在这个实现中，我们首先使用标准库中的 qsort 函数对数组进行排序。排序后，相同的元素会相邻；然后，我们遍历排序后的数组，只保留不重复的元素。这种方法不仅去除了重复元素，还对数组进行了排序，这在某些应用场景中可能是额外的好处。

方法三：使用哈希表

如果我们不关心元素的顺序，并且希望在线性时间内完成去重操作，可以考虑使用哈希表。在C语言中，我们可以使用数组来模拟简单的哈希表，前提是我们知道数组中元素的范围。

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

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

int removeDuplicates(int arr[], int n) {
    bool hash[MAX_ELEMENT] = {false};
    int j = 0;

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

    return j;
}

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

    printf("原始数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    n = removeDuplicates(arr, n);

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

    return 0;
}

这种方法的时间复杂度为 O(n)，其中 n 是数组的长度。这总方法非常高效，但有一个限制：我们需要知道数组中元素的范围，并且这个范围不能太大，否则会消耗过多内存。如果元素范围很大或者包含负数，我们可能需要使用更复杂的哈希表实现。

总结

我们先来分析一下以上几种方法的性能和适用场景：


在实际应用中，我们需要根据具体的需求和数据特征来选择合适的方法。例如，如果数组很小，或者我们的应用对性能要求不高，那么简单的双重循环方法可能就足够了。如果我们需要有序的结果，那么排序后去重的方法会是一个好选择。如果我们处理的是大型数据集，并且不关心元素的顺序，那么哈希表方法可能是最佳选择。

相关文章