初级算法 - 特殊的数组去重-删除排序数组中的重复项

初级算法 - 特殊的数组去重-删除排序数组中的重复项

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。

不要使用额外的数组空间,你必须在原数组上进行修改,并在使用 O(1) 额外空间的条件下完成。

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

对引入的数组进行修改,对原数组的修改是成功的。

①、这里是翻译错误,所以只要返回数组的新长度即可,无论你是否修改了原数组。

var removeDuplicates = function(nums) {
    const n = nums.length;
    if (n < 2) {
        return n;
    }
    let slow = 1;
    for (let i = 1; i < n; i++) {
        if (nums[i] !== nums[i - 1]) {
            nums[slow] = nums[i];
            slow++;
        }
    }
    return slow;
};

存储当前元素,同时比较遍历的每一个元素,如果不同,则存储该元素,并将其作为下一循环的参照对象进行比较。

同时循环次数加1,该数值等同于新数组长度。直至循环完毕。这里是统计了应该保存的元素的出现次数,如果放入数组,则对应数组索引(这里只是为了更好的解释,实际上应该slow !== 次数)。

如同原因导致,这里返回的slow只是在推理中应该是新数组的长度,并不是真正意义上的数组长度。如果你此时打印nums,发现其总长度并没有改变,只是顺序发生了改变。

在上方的代码中,nums[slow]的值在某一定时间总是是不变的,这是参照物。

nums[i]则是比较的每一个元素,如果不等于nums[slow],那么就发现了一个从未发现过的新鲜元素。同时num[i]继续向数组后方循环,直至寻找到所有不重复的元素。

这也叫做双指针。

1551627371615_.pic3fd4e8cfef6295a81de5b0f22a2f0349

右指针一直往右移动,并且时刻与左指针的数据进行比较。

  • 如果相同,左指针不动
  • 如果右指针指向的值不等于左指针指向的值,那么左指针往右移一步,然后再把右指针指向的值赋给左指针。当然,我们这里只用统计左指针曾经指向过的值即可。
# 算法 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×