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

c语言去掉数组中重复的元素（附带源码和解析）

在C语言中，去掉数组中重复的元素是一个常见的编程任务，这个过程通常被称为数组去重。去重的原理是遍历数组，识别并保留唯一元素，同时移除或忽略重复出现的元素。
 

数组去重的基本思路是使用两个循环：外层循环遍历数组中的每个元素，内层循环则负责将当前元素与其后的所有元素进行比较。如果发现重复元素，我们就将其后的所有元素向前移动一位，覆盖掉重复的元素。这个过程会不断重复，直到处理完所有元素。


下面是一个实现数组去重的 C 语言函数示例：

#include <stdio.h>

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

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

    return newSize;
}

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

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

    int newSize = removeDuplicates(arr, n);

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

    return 0;
}

这段代码的输出结果如下：

原始数组：1 2 2 3 4 4 4 5 5 
去重后的数组：1 2 3 4 5

让我们详细解析一下这个去重函数的工作原理：


这种方法的优点是它不需要额外的存储空间，直接在原数组上进行操作。然而，它要求输入数组是有序的；如果输入数组是无序的，我们需要先对数组进行排序，然后再应用这个算法。
 

对于无序数组，我们可以使用另一种方法：使用一个辅助数组来存储唯一元素。这种方法的时间复杂度较高，但不要求输入数组有序。以下是一个处理无序数组的去重函数：

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

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

    return newSize;
}

这个函数的工作原理是：对于数组中的每个元素，我们检查它是否已经存在于新数组（即前 newSize 个元素）中，如果不存在，我们就将它添加到新数组的末尾。这种方法的时间复杂度是 O(n^2)，但它可以处理无序数组。
 

在实际应用中，选择哪种去重方法取决于多个因素，如数组是否有序、数组的大小、可用的内存空间等。对于大型数组，可能需要考虑更高效的算法，如使用哈希表来检测重复元素，这可以将时间复杂度降低到 O(n)，但会增加空间复杂度。
 

总之，数组去重是一个看似简单，但实际上有多种实现方式的问题。

相关文章