c语言数组的冗余祛除

### C语言中去除数组冗余元素的方法 在C语言中，可以通过遍历数组并利用辅助数据结构来实现去重操作。以下是几种常见的方法： #### 方法一：双层循环比较 通过两层嵌套循环逐一比较数组中的每个元素是否重复，并将不重复的元素存储到一个新的数组中。 ```c #include <stdio.h> void removeDuplicates(int arr[], int *size) { int temp[*size]; int newSize = 0; for (int i = 0; i < *size; i++) { bool isDuplicate = false; for (int j = 0; j < newSize; j++) { if (temp[j] == arr[i]) { isDuplicate = true; break; } } if (!isDuplicate) { temp[newSize++] = arr[i]; } } // 将结果复制回原数组 for (int i = 0; i < newSize; i++) { arr[i] = temp[i]; } *size = newSize; } int main() { int arr[] = {1, 2, 3, 2, 4, 5, 1}; int size = sizeof(arr) / sizeof(arr[0]); printf("Original array:\n"); for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); removeDuplicates(arr, &size); printf("Array after removing duplicates:\n"); for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; } ``` 这种方法的时间复杂度为 \(O(n^2)\)，适用于较小规模的数据集[^1]。 --- #### 方法二：排序后单次扫描 先对数组进行排序，然后通过一次线性扫描移除相邻的重复项。此方法依赖于标准库函数 `qsort` 实现排序功能。 ```c #include <stdio.h> #include <stdlib.h> // 比较函数用于 qsort 排序 int compare(const void *a, const void *b) { return (*(int *)a - *(int *)b); } void removeDuplicatesSorted(int arr[], int *size) { qsort(arr, *size, sizeof(int), compare); // 对数组进行升序排列 int newSize = 1; for (int i = 1; i < *size; i++) { if (arr[i] != arr[newSize - 1]) { arr[newSize++] = arr[i]; } } *size = newSize; } int main() { int arr[] = {1, 2, 3, 2, 4, 5, 1}; int size = sizeof(arr) / sizeof(arr[0]); printf("Original array:\n"); for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); removeDuplicatesSorted(arr, &size); printf("Array after removing duplicates using sorting method:\n"); for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; } ``` 该算法时间复杂度主要由排序决定，通常为 \(O(n \log n)\)[^2]。 --- #### 方法三：哈希表（需额外空间） 如果允许使用更多内存资源，则可以借助布尔型标志位或者更高级别的散列表技术标记已访问过的数值。下面展示了一个简单的基于固定范围整数集合的例子。 ```c #define MAX_VALUE 100 void removeDuplicatesHashing(int arr[], int *size) { int hashTable[MAX_VALUE + 1] = {0}; // 初始化全零状态 int index = 0; for (int i = 0; i < *size; ++i) { if (hashTable[arr[i]] == 0) { arr[index++] = arr[i]; hashTable[arr[i]]++; } } *size = index; } int main() { int arr[] = {1, 2, 3, 2, 4, 5, 1}; int size = sizeof(arr) / sizeof(arr[0]); printf("Original array:\n"); for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); removeDuplicatesHashing(arr, &size); printf("Array after removing duplicates with hashing technique:\n"); for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; } ``` 这里假设输入值都在 `[0..MAX_VALUE]` 范围之内；否则需要动态分配更大的连续区域作为映射目标[^3]。 --- 以上三种方式各有优劣，在实际应用过程中可以根据具体场景需求选取最合适的解决方案。