C语言实现O(nlogn)复杂度的数组重复元素移至末尾并保序

问题需求 #

在C语言中实现将数组的重复元素移至末尾，同时保持原数组的元素顺序，时间复杂度必须为O(nlogn)。

限制条件 #

• 必须保持原数组的元素顺序
• 仅可使用1个辅助数组
• 数组中值的范围未知，可能远大于数组大小n
• 所有值均为正数
• 时间复杂度要求为O(nlogn)

示例 #

原数组：arr = {7, 3, 1, 2, 7, 9, 3, 2, 5, 9, 6, 2}，n=12
结果数组：arr = {7, 3, 1, 2, 9, 5, 6, 2, 9, 2, 3, 7}

当前进展与卡点 #

已完成步骤：

1. 将原数组复制到临时数组
2. 使用快速排序对临时数组排序
3. 将临时数组中的重复元素移至末尾

卡点：无法通过临时数组与原数组的对比，完成最终的数组重排逻辑。

现有代码 #

int findDulpilcatesV2(int* arr, int n) {
    int i, * tempArr, j = 0, countNonRepeatEl = 0, searchKeyIndex, elIndex;

    tempArr = (int*)calloc(n, sizeof(int));
    assert(tempArr);

    // Saving original array in temp array
    for (i = 0; i < n; i++)
    {
        tempArr[i] = arr[i];
    }

    // Sorting temp array
    quickSort(tempArr, 0, n - 1);

    // Move duplicates to the end
    for (i = 0; i < n; i++)
    {
        if (tempArr[i] != tempArr[i+1])
        {
            swap(&tempArr[j], &tempArr[i]);
            countNonRepeatEl++;
            j++;
        }
    }


    free(tempArr);
    tempArr = NULL;
    return countNonRepeatEl;
}

解决方案 #

你的思路方向正确，但缺少跟踪原数组元素首次出现状态，并区分首次/重复元素放置位置的核心逻辑。以下是符合所有限制条件的完整实现：

核心思路 #

1. 复制原数组到临时数组并排序，利用排序后的数组快速查询元素的出现范围。
2. 利用原数组元素均为正数的特性，在临时数组中标记已处理过的元素（设为负数），避免额外辅助空间。
3. 使用双指针遍历原数组：front指针负责放置首次出现的元素，back指针负责放置重复元素。

完整实现代码 #

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

// 快速排序实现（保证O(nlogn)时间复杂度）
void quickSort(int* arr, int low, int high) {
    if (low < high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;
        int pi = i + 1;
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 二分查找获取元素首次出现的索引
int findFirstOccurrence(int* arr, int n, int target) {
    int low = 0, high = n - 1;
    int result = -1;
    while (low <= high) {
        int mid = low + (high - low)/2;
        if (arr[mid] == target) {
            result = mid;
            high = mid - 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

// 二分查找获取元素最后出现的索引
int findLastOccurrence(int* arr, int n, int target) {
    int low = 0, high = n - 1;
    int result = -1;
    while (low <= high) {
        int mid = low + (high - low)/2;
        if (arr[mid] == target) {
            result = mid;
            low = mid + 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

int moveDuplicatesToEnd(int* arr, int n) {
    int* tempArr = (int*)malloc(n * sizeof(int));
    assert(tempArr != NULL);

    // 复制原数组到临时数组
    for (int i = 0; i < n; i++) {
        tempArr[i] = arr[i];
    }

    // 排序临时数组
    quickSort(tempArr, 0, n - 1);

    int front = 0;
    int back = n - 1;

    for (int i = 0; i < n; i++) {
        int current = arr[i];
        int firstIdx = findFirstOccurrence(tempArr, n, current);

        if (tempArr[firstIdx] > 0) { // 正数表示未处理，即首次出现
            // 将首次出现的元素放到数组前端
            arr[front++] = current;
            // 标记该元素的所有出现位置为已处理（设为负数）
            int lastIdx = findLastOccurrence(tempArr, n, current);
            for (int j = firstIdx; j <= lastIdx; j++) {
                tempArr[j] = -tempArr[j];
            }
        } else {
            // 重复元素放到数组末尾
            arr[back--] = current;
        }
    }

    free(tempArr);
    // 返回前端非重复（首次出现）元素的个数
    return front;
}

// 测试示例
int main() {
    int arr[] = {7, 3, 1, 2, 7, 9, 3, 2, 5, 9, 6, 2};
    int n = sizeof(arr)/sizeof(arr[0]);

    int nonRepeatCount = moveDuplicatesToEnd(arr, n);

    printf("处理后的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n前端非重复元素个数：%d\n", nonRepeatCount);

    return 0;
}

复杂度说明 #

• 时间复杂度：排序O(nlogn) + 每个元素两次二分查找O(logn) + 遍历原数组O(n)，总复杂度为O(nlogn)，符合要求。
• 空间复杂度：仅使用1个辅助数组tempArr，满足限制条件。

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