C++数组去重：removeDup函数重复元素定位逻辑修复求助

实现效率说明 #

你当前写的双层嵌套循环时间复杂度是O(n²)，不是最高效的实现方案：

• 如果不限制空间占用，用哈希表统计元素出现频率，单次遍历即可完成处理，时间复杂度O(n)，空间复杂度O(n)
• 针对你给出的已排序数组场景，不需要额外空间，用单次遍历的分段扫描就能实现，时间复杂度O(n)，空间复杂度O(1)，是当前场景下的最优方案。

现有代码的逻辑问题 #

你现在的逻辑缺陷不是「找不到最后一个重复元素」这么简单，核心问题有两个：

1. 仅用一个temp变量存储重复值，无法区分多组不同的重复元素。你的测试用例里20、40、50都是重复值，单个变量根本无法完成多组重复标记。
2. 内层循环遍历过程中直接修改arr[i]的值，会打乱原数组的有序结构，导致后续比较判断完全失效。
   你设想的「标记重复元素再移位到末尾」的思路不需要专门定位最后一个重复元素，只要在遍历过程中识别出所有重复段，直接跳过重复段、保留非重复段即可，逻辑更简单也不容易出错。

另外从你给出的预期输出10,30来看，你要实现的不是常规的「重复元素保留1份」的去重，而是删除所有出现次数≥2的元素，仅保留只出现过1次的元素，和常规去重逻辑有区别。

适配需求的最优实现 #

针对有序数组、仅保留单次出现元素的需求，直接用分段扫描的方式实现即可：

int removeDup(int arr[], int n)
{
    if (n <= 1) return n;
    int slow = 0; // 指向结果数组的待写入位置
    int i = 0;
    while (i < n) {
        int j = i;
        // 扫描连续相同元素的结束位置
        while (j < n && arr[j] == arr[i]) {
            j++;
        }
        // 连续段长度为1，说明元素无重复，写入结果位置
        if (j - i == 1) {
            arr[slow] = arr[i];
            slow++;
        }
        // 跳到下一个不同值的起始位置
        i = j;
    }
    // 返回值为去重后数组的长度，数组前slow位即为最终结果
    return slow;
}

传入你的测试用例int arr[] = {10, 20, 20, 30, 40, 40, 40, 50, 50}时，函数返回值为2，数组前2位正好是预期的10, 30。

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