有序数组去重并移重复项至末尾：无额外数组实现遇阻求助

问题背景 #

需要实现：将有序数组中的所有重复项移动到数组末尾，要求不使用额外数组（原地操作），目前仅掌握使用额外数组的实现方式，对原地解法的指针运用存在困惑。

尝试的错误代码（无法正常运行） #

int main()
{
    int newArr[12] =  {};
    int n = 12;
    int first = 0;
    int last = n - 1;
    int* D = arr + 1; // 未定义arr直接引用，编译报错
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        j = i + 1;

        while (j < n)
        {
            if (newArr[i] != *D)
            {
                D++;
            }
            if (newArr[i] == *D)
            {
                swap(&newArr[i], &newArr[last]);
                j++;
                last--;
            }
            j++;
        }
    }
    for (int i = 0; i < n; i++)
    {
        printf("%d", newArr[i]);
    }
}

这段代码的核心问题：

• 未定义arr就直接使用int* D = arr + 1，触发编译错误；
• 逻辑混乱：指针D的移动和j的遍历无关联，重复判断条件会导致错误交换，无法正确识别连续重复元素。

可运行的双数组版本代码 #

int moveDuplicatesV1(int* arr, int n)
{
    int* seen_before = (int*)calloc(n * 2 + 1, sizeof(int));
    assert(seen_before);
    int val = 0, count = 0, flag = 1;
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        val = arr[i];
        if (seen_before[arr[i] + n] == 0)
        {
            seen_before[arr[i] + n]++;
            count++;
            continue;
        }
        else if (flag)
        {
            j = i + 1;
            flag = 0;
        }
        while (j < n)
        {
            if (seen_before[arr[j] + n] == 0)
            {
                count++;
                seen_before[arr[j] + n]++;
                swap(&arr[i], &arr[j]);
                j++;
                if (j == n)
                {
                    free(seen_before);
                    return count;
                }
                break;
            }
            j++;
            if (j == n)
            {
                free(seen_before);
                return count;
            }
        }
    }
}

原地解法（无额外数组） #

利用数组有序的特性（重复元素必然连续），用双指针即可实现原地操作：

思路

1. 用unique_ptr标记当前最后一个不重复元素的位置，初始值为0；
2. 遍历指针i从1开始，逐个检查元素；
3. 若arr[i]与arr[unique_ptr]不相等，说明是新的不重复元素：
   • 将unique_ptr后移一位；
   • 交换arr[unique_ptr]和arr[i]，把不重复元素移到前面区域；
4. 遍历结束后，unique_ptr + 1即为不重复元素的数量，数组从unique_ptr + 1到末尾的部分都是重复项。

实现代码

void moveDuplicatesInPlace(int* arr, int n) {
    if (n <= 1) return; // 数组长度≤1无需处理

    int unique_ptr = 0;
    for (int i = 1; i < n; i++) {
        // 遇到不重复元素
        if (arr[i] != arr[unique_ptr]) {
            unique_ptr++;
            // 避免自身交换的无意义操作
            if (unique_ptr != i) {
                int temp = arr[unique_ptr];
                arr[unique_ptr] = arr[i];
                arr[i] = temp;
            }
        }
    }
    // arr[0..unique_ptr] 为不重复元素，arr[unique_ptr+1..n-1] 为重复项
}

// 测试示例
int main() {
    int arr[] = {1,1,2,2,3,4,4,4,5};
    int n = sizeof(arr)/sizeof(arr[0]);
    moveDuplicatesInPlace(arr, n);
    
    printf("处理后数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    // 输出：处理后数组：1 2 3 4 5 1 2 4 4 
    return 0;
}

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