将重复元素移至数组末尾的O(n)非递归C函数实现求助

需求说明 #

实现一个非递归函数，接收两个参数：

• 整数数组
• 表示数组大小的整数

函数需将数组中的重复元素移至数组末尾，同时返回数组中不同元素的数量。

示例 #

输入数组：[5, 2, 4, 5, 6, 7, 2]，数组大小n=7
处理后数组：[5, 2, 4, 6, 7, 5, 2]
返回值：5

约束要求 #

• 必须保留原数组中非重复元素的原有顺序（如示例中5需保持初始位置）
• 重复元素的排列顺序无要求，仅需保证非重复元素顺序不变
• 函数返回不同元素的数量
• 数组元素的取值范围为[-n, n]
• 仅允许使用一个辅助数组
• 时间复杂度必须为O(n)

你的代码问题分析 #

int moveDup(int* arr, int n)
{
    int* C = (int*)calloc(n * 2 + 1, sizeof(int));
    assert(C);
    /*int* count = C + n;*/
    int *D = arr[0]; // 错误：arr[0]是int类型，不能赋值给指针，应改为int *D = arr;
    int value = 0, count = 0;
    for (int i = 0; i < n; i++)
    {
        value = arr[i];
        if (C[value + n] == 0)
        {
            *D = arr[i];
            D++;
            count++;
        }
        C[value + n] = C[value + n] + 1;
    }
    // 错误：此循环仅处理最后一个value的重复项，未遍历所有元素的重复情况，且*D = i是错误赋值
    while (1 < C[value + n])
    {
        *D = i;
        D++;
        C[value + n]--;
    }
    free(C);
    return count;
}

核心问题点 #

1. 指针初始化错误：int *D = arr[0]; 类型不匹配，arr[0]是数组第一个元素的整数值，不能直接赋值给指针变量，正确写法是int *D = arr;，让D指向数组起始位置。
2. 重复元素收集逻辑缺失：第二个循环仅处理了最后一个遍历到的元素的重复项，没有遍历整个数组来收集所有重复出现的元素，导致数组后半部分未被正确填充。
3. 错误的赋值操作：*D = i; 把循环变量i赋值给数组，而不是原数组中的重复元素值，完全不符合需求。

修正后的代码实现 #

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

int moveDup(int* arr, int n)
{
    // 辅助数组，索引范围0~2n，对应元素值-n~n
    int* countArr = (int*)calloc(n * 2 + 1, sizeof(int));
    assert(countArr);

    int* dest = arr; // 指向非重复元素的存储位置
    int uniqueCount = 0;

    // 第一次遍历：统计元素出现次数，同时把首次出现的元素放到数组前半部分
    for (int i = 0; i < n; i++)
    {
        int val = arr[i];
        int idx = val + n; // 转换为非负索引
        if (countArr[idx] == 0)
        {
            *dest = val;
            dest++;
            uniqueCount++;
        }
        countArr[idx]++;
    }

    // 第二次遍历：收集所有重复出现的元素，放到数组后半部分
    for (int i = 0; i < n; i++)
    {
        int val = arr[i];
        int idx = val + n;
        if (countArr[idx] > 1)
        {
            *dest = val;
            dest++;
            countArr[idx]--; // 每放一个重复元素，计数减1，避免重复放入过多
        }
    }

    free(countArr);
    return uniqueCount;
}

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

    printf("处理后数组：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n不同元素数量：%d\n", unique);
    return 0;
}

代码说明 #

1. 辅助数组初始化：利用calloc初始化大小为2n+1的辅助数组，确保初始值全为0，用于统计每个元素的出现次数，通过val + n将负数值转换为合法的非负索引。
2. 第一次遍历：遍历数组，将首次出现的元素依次放到数组前半部分，同时统计每个元素的出现次数，记录不同元素的数量uniqueCount。
3. 第二次遍历：再次遍历原数组，将重复出现的元素（即计数大于1的元素）依次放到数组后半部分，每放入一个重复元素就将对应计数减1，确保每个重复元素的出现次数与原数组一致。
4. 内存释放：使用完辅助数组后及时释放内存，避免内存泄漏。

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