LeetCode第26题移除有序数组重复项时遇运行时错误求助

错误原因分析 #

• 空vector下标访问越界：temp初始化为空vector，直接使用temp[i] = nums[i]赋值会触发运行时错误。vector的下标访问仅对已分配内存的有效位置生效，空vector没有任何元素，此时访问下标0属于非法内存操作。
• while循环下标越界：循环条件j <= temp.size()错误，当j等于temp.size()时，temp[j]访问的是vector末尾之后的位置，超出了有效下标范围（有效下标应为0到temp.size()-1）。
• 去重逻辑完全错误：原数组是有序数组，代码逻辑既没有利用有序性，也没有实现去重：
  • 当nums[i] > temp[j]时直接覆盖temp[j]会破坏temp的有序性；
  • else分支的continue不会终止循环，会导致j一直不变，陷入死循环。
• 返回值不符合要求：题目要求返回去重后的数组长度，代码返回的是原nums的大小，完全不符合题意。

修复方案 #

方案1：双指针法（原地修改，空间复杂度O(1)，符合题目最优要求） #

利用有序数组重复元素相邻的特性，用慢指针k记录去重后数组的末尾位置，快指针i遍历整个数组：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int k = 0; // 慢指针，指向去重后数组的最后一个元素
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] != nums[k]) {
                k++;
                nums[k] = nums[i];
            }
        }
        return k + 1; // 去重后的数组长度
    }
};

方案2：临时vector的正确实现（空间复杂度O(n)，仅作参考） #

如果一定要用临时vector，需保证正确添加元素并利用有序性判断重复：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        vector<int> temp;
        for (int num : nums) {
            // 有序数组中，只需判断temp最后一个元素是否与当前元素相同
            if (temp.empty() || num != temp.back()) {
                temp.push_back(num);
            }
        }
        // 将去重后的结果复制回原数组
        nums.assign(temp.begin(), temp.end());
        return temp.size();
    }
};

关键说明 #

• 题目要求原地修改数组，双指针法是最优解，空间复杂度为O(1)；
• 有序数组的特性是解题核心，无需额外遍历临时数组判断重复，只需比较相邻或最后一个元素即可。

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