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

题目：

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

示例1
给定数组 nums = [1,1,2], 
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
你不需要考虑数组中超出新长度后面的元素。

示例2
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

解题思路

提取题目中的重要的名词，排序数组、原地删除、返回长度和不要使用额外数组空间。也就是说我们需要：

1. 排序：数组有序的。
2. 去重：有序数组去重，只需要判断前后数是否相等即可。
3. 原地删除：必须操作的是原数组。
4. 返回长度：返回的是长度而不是去重后的数组。

代码

暴力破解法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
 var removeDuplicates = function(nums) {
  for(var i = 0;i < nums.length;i++){
      if(nums[i+1] != 'undefined' && nums[i+1] === nums[i]){   // 判断前后是否相等 
          let index = nums.indexOf(nums[i]);
          nums.splice(index,1);  // 原地删除
          i = i-1;
      }
  }
  return nums.length;  // 返回长度
};

暴力破解法就是抓住这些关键字，然后逐条逐条地去实现即可。但是我们可以看到，在for循环中需要使用indexOf进行查找，然后又需要使用splice进行分割，它们底层都是O(n)级别。那么我们可不可以使用更加简单的方法了。这时候我们就需要重新审查题目，看看有没有漏掉其他的关键信息。
改进方法
我们看到示例中多次提到你不需要考虑数组中超过新长度后面的元素，只需要确保原数组的前n个元素能够被去重。 这是什么意思了？之前我们原地删除重复元素，必须先通过indexOf找到这个元素，然后在这个元素的位置删除它。现在我们可以只找出数组中的不重复元素，然后把这些不重复元素移动到数组最前面，至于后面的元素是否重复我们就不需要管了。

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

我们只需要定义一个指针来记录数组中当前不重复的元素位置，我们查找到不重复元素就把它赋值为下一个位置即可。