C语言数组去重函数时间复杂度分析及代码优化咨询

一、时间复杂度验证：你的推导正确，实际为O(n²) #

假设你的代码是这类常见的嵌套循环+元素移动实现（如下示例）：

void removeDuplicates(int arr[], int *n) {
    int i, j, k;
    for (i = 0; i < *n; i++) {
        for (j = i + 1; j < *n; ) {
            if (arr[j] == arr[i]) {
                // 重复元素后移覆盖
                for (k = j; k < *n - 1; k++) {
                    arr[k] = arr[k + 1];
                }
                (*n)--;
            } else {
                j++;
            }
        }
    }
}

你最初认为是O(n³)，是因为直观看到三层嵌套循环，但实际上内层循环的总执行次数并非n³量级：

• 外层循环执行n次（最坏情况）；
• 中间层循环遍历后续元素，但每次发现重复时会缩短数组长度；
• 关键在于每个元素最多被向前移动一次，整个过程中所有元素的移动总次数是O(n²)（最坏情况如全重复数组，总移动次数为n+(n-1)+...+1 = n(n+1)/2）；
• 元素相等判断的总次数也是O(n²)（最坏情况每个元素和后面所有元素对比）。

因此整体时间复杂度为O(n²)，你的推导完全正确。

二、代码改进建议 #

1. 排序后去重（O(n log n) 时间复杂度） #

排序后重复元素相邻，仅需一次遍历即可完成去重，效率远高于O(n²)实现：

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

// qsort 比较函数
int compareInts(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

void removeDuplicatesSorted(int arr[], int *n) {
    if (*n <= 1) return;
    
    qsort(arr, *n, sizeof(int), compareInts);
    
    int uniqueIdx = 0;
    for (int i = 1; i < *n; i++) {
        if (arr[i] != arr[uniqueIdx]) {
            uniqueIdx++;
            arr[uniqueIdx] = arr[i];
        }
    }
    *n = uniqueIdx + 1;
}

该方案适合大多数场景，尤其是数据量较大时，唯一缺点是会改变元素原始顺序。

2. 哈希表去重（平均O(n) 时间复杂度） #

利用哈希表记录已出现的元素，一次遍历完成去重，时间效率最优：

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

void removeDuplicatesHash(int arr[], int *n) {
    if (*n <= 1) return;
    
    // 先确定元素范围，用数组模拟哈希表
    int min = arr[0], max = arr[0];
    for (int i = 1; i < *n; i++) {
        if (arr[i] < min) min = arr[i];
        if (arr[i] > max) max = arr[i];
    }
    
    int range = max - min + 1;
    bool *seen = calloc(range, sizeof(bool));
    if (!seen) return;
    
    int uniqueIdx = 0;
    for (int i = 0; i < *n; i++) {
        int hashIdx = arr[i] - min;
        if (!seen[hashIdx]) {
            seen[hashIdx] = true;
            arr[uniqueIdx++] = arr[i];
        }
    }
    
    *n = uniqueIdx;
    free(seen);
}

该方案平均时间复杂度O(n)，但需要额外空间存储哈希表。若元素范围过大，可使用动态哈希库（如uthash）替代数组模拟。

3. 优化原有O(n²)实现 #

若需保留元素原始顺序且数据量较小，可优化原逻辑减少元素移动次数：

void removeDuplicatesOptimized(int arr[], int *n) {
    if (*n <= 1) return;
    
    int uniqueIdx = 0;
    for (int i = 0; i < *n; i++) {
        bool isDuplicate = false;
        // 仅和已保留的唯一元素对比
        for (int j = 0; j < uniqueIdx; j++) {
            if (arr[i] == arr[j]) {
                isDuplicate = true;
                break;
            }
        }
        if (!isDuplicate) {
            arr[uniqueIdx++] = arr[i];
        }
    }
    *n = uniqueIdx;
}

这种写法避免了每次发现重复就移动后续元素，而是先收集所有唯一元素，最后调整数组长度，实际执行效率比原写法更高。

三、总结 #

你的推导正确，原函数实际时间复杂度为O(n²)。根据场景选择合适的改进方案：大数据量优先选排序或哈希表去重；需保留原始顺序且数据量小则用优化后的O(n²)实现。

内容的提问来源于stack exchange，提问作者krotovukha