[算法题]删除排序数组中的重复项

[Geek-James]

leetCode 26题 删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

原地算法，就是不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入的一种算法操作。

在不复制数组的情况下从数组中删除元素的一些提示：

• 尝试双指针法。
• 你是否使用“元素顺序可以更改”这一属性？
• 当要删除的元素很少时会发生什么？

方法一:双指针 效率一般

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

方法二:用js的array的splice方法 效率一般

var removeDuplicates = function(nums) {
  var cur = nums[0];
    for (var i = 1; i < nums.length;) {
        if (nums[i] === cur)
            nums.splice(i, 1);
        else
            cur = nums[i++];
    }
    return nums.length
};

方法三:巧用冒泡 效率高

var removeDuplicates = function(nums) {
    var A=0;
    for (var n=1;n<nums.length;n++)
    {
        if (nums[n]!=nums[A]){
           nums[++A]=nums[n]; 
        }
    }
        
 return A+1;
};