C语言编程题移除数组中的重复元素

C语言中移除数组中的重复元素可以使用多种方法。方法各有优缺点,选择合适的方法取决于具体需求和数据特征。在实际应用中,需要考虑时间复杂度、空间复杂度以及对原始数组顺序的要求。

1、使用临时数组

这种方法适用于不修改原始数组顺序的情况。

#include <stdio.h>

void removeDuplicates(int arr[], int *size) {
    int temp[*size];
    int j = 0;

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

    for (int i = 0; i < j; i++) {
        arr[i] = temp[i];
    }

    *size = j;
}

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

    removeDuplicates(arr, &size);

    printf("Array after removing duplicates:\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

2、使用双重循环

这种方法直接在原始数组上操作,但时间复杂度较高。

#include <stdio.h>

void removeDuplicates(int arr[], int *size) {
    for (int i = 0; i < *size; i++) {
        for (int j = i + 1; j < *size;) {
            if (arr[j] == arr[i]) {
                for (int 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};
    int size = sizeof(arr) / sizeof(arr[0]);

    removeDuplicates(arr, &size);

    printf("Array after removing duplicates:\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

3、使用标记数组

这种方法适用于数组元素有限且较小的情况。

#include <stdio.h>

void removeDuplicates(int arr[], int *size) {
    int hash[256] = {0}; // Assuming array elements are within 0-255

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

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

    removeDuplicates(arr, &size);

    printf("Array after removing duplicates:\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

4、使用排序法

先对数组进行排序,然后再移除相邻的重复元素。

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

// Comparison function for qsort
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

void removeDuplicates(int arr[], int *size) {
    qsort(arr, *size, sizeof(int), compare);

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

    *size = j;
}

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

    removeDuplicates(arr, &size);

    printf("Array after removing duplicates:\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

5、使用集合(Set)

这种方法利用集合的特性来去除重复元素,需要额外的空间来存储元素。

#include <stdio.h>

void removeDuplicates(int arr[], int *size) {
    int hash[1000] = {0}; // Assuming array elements are within 0-999
    int result[*size];
    int j = 0;

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

    for (int i = 0; i < j; i++) {
        arr[i] = result[i];
    }

    *size = j;
}

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

    removeDuplicates(arr, &size);

    printf("Array after removing duplicates:\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

推荐阅读
cjavapy编程之路首页