数组去重c语言

### C语言实现数组去重方法 #### 方法一：辅助数组法 通过创建一个辅助数组来存储已经去重的元素。对于每一个新读取的元素，将其与辅助数组中的已有元素逐一比较。如果没有发现重复，则将此元素加入辅助数组。 这种方法的时间复杂度较高，在最坏的情况下为 \(O(n^2)\)[^1]。以下是基于该逻辑的一个简单实现： ```c #include <stdio.h> void removeDuplicates(int *arr, int size, int *result, int *resSize) { *resSize = 0; for (int i = 0; i < size; ++i) { bool isDuplicate = false; for (int j = 0; j < *resSize; ++j) { if (arr[i] == result[j]) { isDuplicate = true; break; } } if (!isDuplicate) { result[*resSize] = arr[i]; (*resSize)++; } } } int main() { int array[] = {1, 2, 3, 2, 4, 5, 1}; int size = sizeof(array)/sizeof(array[0]); int result[size]; int resSize; removeDuplicates(array, size, result, &resSize); printf("After removing duplicates:\n"); for (int i = 0; i < resSize; ++i) { printf("%d ", result[i]); } return 0; } ``` #### 方法二：排序加单次遍历 首先对数组进行排序，之后只需一次线性扫描即可去除相邻的重复项。这种策略的前提是对数组进行了预排序，因此整体时间复杂度主要取决于所使用的排序算法。通常采用快速排序或其他高效的排序技术，使得整个过程达到 \(O(n \log n)\)[^2] 的效率。 下面是一个例子展示如何结合冒泡排序完成这一目标: ```c #include<stdio.h> #define MAX_SIZE 100 // Bubble Sort Function void bubbleSort(int A[], int N){ int temp; for(int pass=1;pass<N-1;pass++) for(int i=0;i<N-pass;i++) if(A[i]>A[i+1]){ temp=A[i]; A[i]=A[i+1]; A[i+1]=temp; } } int eliminateDupesAndCount(int sortedArr[], int length){ int uniqueIndex = 0; for(int index=1;index<length;index++){ if(sortedArr[index]!=sortedArr[uniqueIndex]){ uniqueIndex++; sortedArr[uniqueIndex]=sortedArr[index]; } } return uniqueIndex + 1; } int main(){ int M,n,i,j,k,a[MAX_SIZE]; scanf("%d",&M); while(M--){ scanf("%d",&n); for(i=0;i<n;i++)scanf("%d",&a[i]); bubbleSort(a,n); k = eliminateDupesAndCount(a,n); for(i=0;i<k;i++)printf("%d ",a[i]); puts(""); } return 0; } ``` #### 方法三：哈希表（Set）去重 当需要更高效的方式时，可以考虑引入额外的空间开销——即构建一个散列表或集合(Set)，用于记录哪些数值已经被访问过。这种方式能够显著降低查找是否存在的成本至常数级别\(O(1)\),从而使总体性能提升到接近线性的水平\(O(n)\)[^4]。 由于标准C库并不直接提供内置的支持结构像其他高级编程语言那样拥有专门的数据类型比如Python里的`set`,所以这里我们模拟了一个简易版本的功能演示如下所示： ```c #include <stdbool.h> #include <stdio.h> bool hashTable[10000]; // Assuming values are within this range. void initializeHashTable(bool table[]) { for (size_t i = 0; i < sizeof(hashTable)/sizeof(hashTable[0]); ++i) { table[i] = false; } } void removeDupsUsingHash(int inputArray[], int lenInput, int outputArray[]) { int posOutput = 0; initializeHashTable(hashTable); for (int idxInp = 0; idxInp < lenInput; ++idxInp) { if(!hashTable[inputArray[idxInp]]) { hashTable[inputArray[idxInp]] = true; outputArray[posOutput++] = inputArray[idxInp]; } } } int main(void) { int originalData[] = {97, 86, 97, 86, 45, 32, 45}; const int LENGTH_ORIGINAL_DATA = sizeof(originalData)/sizeof(*originalData); int deduplicatedData[LENGTH_ORIGINAL_DATA]; removeDupsUsingHash(originalData, LENGTH_ORIGINAL_DATA, deduplicatedData); for (int idxOut = 0; idxOut < LENGTH_ORIGINAL_DATA && hashTable[deduplicatedData[idxOut]]; ++idxOut) { printf("%d ", deduplicatedData[idxOut]); } return 0; } ```