力扣每日一题-移除元素（与删除排序数组中的重复项）

题目

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

示例 1:

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

题解

(1)使用双指针，简直好简单。指针i = 0，指针n = 数组长度。找到目标数换最后位数，长度-1，相当于删除。继续与目标数比较，返回n

var removeElement = function(nums, val) {
    for (var i = 0, n = nums.length; i < n; i++) if(nums[i] === val) nums[i--] = nums[n-- - 1]
    return n
};

快慢指针：

// 双指针
var removeElement = function(nums, val) {
    let fast = 0, slow = 0;
    while(fast < nums.length ) {
        if (nums[fast] !== val) {
            nums[slow] = nums[fast];
            slow ++;
        }
        fast ++;
    }
    return slow;
};

(2)使用splice函数，本人一开始就是这么做的，奈何没有想到的一点是，splice函数中数组中元素删除后会自动更新数组，索引值就变了，和以前的数组不一样了。这样在循环的时候，就会出现问题，但是当时没有想到可以用两个变量，一个进行循环，一个进行计数。代码如下：

var removeElement = function(nums, val) {
 if (nums.length === 0 || !nums) return 0

    let i = 0
    let len = nums.length
    
    for (let j = 0; j < len; j++) {

        if (nums[i] !== val) {
            i++
        } else {
            nums.splice(i, 1)
            len++
        }

    }
    return i + 1
};

这里还有一个高级的用法，就是倒序循环，这样使用splice函数的时候，就不需要在乎索引的问题了，索引是向前缩进，不影响倒序的循环。（不得不说一句，聪明的人好多，可是我却不是。呜呜呜！）

var removeElement = function(nums, val) {
    for (var i=nums.length;i--;){
        if (nums[i] === val){
            nums.splice(i, 1)
        } 
    }
    return nums.length
};

(3)直接就是循环。需要两个变量搞定。

var removeElement = function (nums, val) {
    let len = 0;
    for (item of nums) {
        if (item !== val) {
            nums[len] = item;
            len ++;
        }
    }
    return len;
};

(4)数组移除

var removeElement = function(nums, val) {
    let index = nums.indexOf(val)
    while( index > -1 ) {
        nums.splice(index,1)
        index = nums.indexOf(val)
    }
    return nums.length
};

题目

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

题解

该题思想与上面的移除元素思想雷同，这里直接写想法。（都是自己想的还挺鸡冻哈哈哈哈）

(1)快慢指针法（双指针）

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

这道题目还可以继续使用快慢指针来来解决, 最开始的时候,两个指针都指向第一个数字，如果两个指针指向的数字相同，则快指针向前走一步,如果不同，则两个指针都向前走一步，然后将当前快指针的值赋给慢指针所在的值，这样当快指针走完整个数组后,慢指针当前的坐标+1就是数组中不同数字的个数。

var removeDuplicates = function (nums) {
  // 慢指针初始为0;
  let k = 0;
  // 循环中的变量i是快指针
  for (let i = 0; i < nums.length; i++) {
    // 如果 快慢指针指向的元素不同
    if(nums[i] !== nums[k]) {
      // 慢指针++; 快指针是 循环变量每次都会自增，不需要单独操作
      k++;
      // 将快指针 指向的元素覆盖慢指针当前的元素
      nums[k] = nums[i]
    }
  }
  return k+1;
};

(2)倒序法

var removeDuplicates = function(nums) {
   len = nums.length-1;
   for(i=len;i>=0;i--){
       if(nums[i]==nums[i-1]){
           nums.splice(i,1)
           //i++   后来才发现这是多余的，因为不影响从前往后数的索引
       }
   }
    return nums.length
};

(3)如果借用js原生的api,这个题目中 for 循环遍历一遍数组，如果前一个元素和后一个元素相同 则就地删除这个元素，这里有一个细节，就是原地删除元素之后, 需要将循环变量更新一下。但是这样复杂度就变高了。

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

(4)懂得自然懂

var removeDuplicates = function (nums) {
    var len = 1;
    for (var i = 1; i < nums.length; i++)
        if (nums[i] != nums[i-1]) nums[len++] = nums[i];
    return len
};