问题

给定一个有序数组，要删除数组重复出现的元素，使得每个元素只出现一次，然后返回移除重复数组后的新长度；

示例：

假设给定一个数组 nums = [1,2,4,4]，删除重复出现的元素 4 后，原数组变成 nums = [1, 2, 4]，此时新的数组长度为 3；

解决思路

数组原地操作

数组原地操作，此时无需创建新的数组，只需要在原来的数组上操作即可。相当于首先要找到数组中重复的元素，然后将重复的元素移除，此时就涉及到数组中的删除操作，相关知识点可以看我的另一篇文章 数组的增删改查。

这是一种时间换空间的方法，此时的空间复杂度为 有序数组去重方法，你会几种？ - 图1#card=math&code=O%281%29&id=VcLTf)，时间复杂度为 有序数组去重方法，你会几种？ - 图2#card=math&code=O%28n%5E2%29&id=HNj42)，具体实现可以参考如下代码，其中也详细注释了每一步操作。

  1. /**
  2. * 去除有序数组中重复元素并返回数组的新长度
  3. * @param nums
  4. * @return 删除重复元素后数组的新长度
  5. */
  6. public int removeDuplicates(int[] nums) {
  7.     // 数组初始容量
  8.     int length = nums.length;
  10.     // 我们假定数组最后一个元素是唯一的，然后对于其他的每个元素，如果自身与它后边的数相同，那么就删除这个相同的元素
  11.     for(int i = length - 2; i >= 0; i++){
  12.         // 比较当前元素与其后一个元素是否相等
  13.         if(nums[i] == nums[i + 1]){
  14.             // 若相等，则移除后一位，并将所有元素向前移动一位
  15.             for(int j = i + 1; j < length; j++){
  16.                 num[j - 1] = nums[j];
  17.             }
  18.             length--;
  19.         }
  20.     }
  22.     // 返回数组的新长度
  23.     return length;
  24. }

普通方法

针对数组原地操作算法时间复杂度为 有序数组去重方法，你会几种？ - 图3#card=math&code=O%28n%5E2%29&id=VqGJV)，为降低时间复杂度提高算法效率，可以通过空间换时间的做法，通过定义新的数组，从而实现去除重复元素的目的，此时的时间复杂度为 有序数组去重方法，你会几种？ - 图4#card=math&code=O%28n%29&id=DzoSM)，而空间复杂度也由 有序数组去重方法，你会几种？ - 图5#card=math&code=O%281%29&id=rHgOG) 变成了 有序数组去重方法，你会几种？ - 图6#card=math&code=O%28n%29&id=JRnaE)。但是有几点需要注意：

  1. 临界情况（即数组为空）；
  2. 创建新数组时，需要指定其容量，所以需要先求出原数组中无重复元素时的元素个数；
  3. 最后则是将原数组中未重复的元素赋值给新数组；
  1. /**
  2. * 去除有序数组中重复元素并返回数组的新长度
  3. * @param nums
  4. * @return 删除重复元素后的新数组
  5. */
  6. public int[] removeDuplicates(int[] nums) {
  7.     // 临界情况
  8.     if(nums.length == 0){
  9.         return nums;
  10.     }
  12.     // 先求出数组中无重复时的元素个数
  13.     int size = 0;
  14.     for(int i = 0; i < nums.length; i++){
  15.         if(i == 0 || nums[i] != nums[i - 1]){
  16.             size++;
  17.         }
  18.     }
  20.     // 用于存放不含重复元素的有序数组
  21.     int[] resultArr = new int[size];
  23.     int index = 0;
  24.     for(int i = 0; i < nums.length; i++){
  25.         if(i == 0 || nums[i] != nums[i + 1]){
  26.             resultArr[index++] = nums[i];
  27.         }
  28.     }
  30.     // 返回新的不含重复元素的有序数组
  31.     return resultArr;    
  32. }

双指针

以上的两种方法要么是以时间换空间，要么是以空间换时间，那我们有没有一种折中的办法，既能保证时间复杂度很低，也能保证空间复杂度呢？答案是：当然有！

利用双指针的思想，既可以将空间复杂度控制在 有序数组去重方法，你会几种？ - 图7#card=math&code=O%281%29&id=tZw5E)，也可以将时间复杂度控制在 有序数组去重方法，你会几种？ - 图8#card=math&code=O%28n%29&id=fd9VX)。

  1. /**
  2. * 去除有序数组中重复元素并返回数组的新长度
  3. * @param nums
  4. * @return 删除重复元素后数组的新长度
  5. */
  6. public int removeDuplicates(int[] nums) {
  7.      // 临界情况
  8.     if(nums.length == 0){
  9.         reutrn 0;
  10.     }
  12.     int size = 0;
  13.     for(int i = 1; i < nums.length; i++){
  14.         if(nums[size] != nums[i]){
  15.             nums[++size] = nums[i];
  17.         }
  18.     }    
  20.     // 返回新长度
  21.     return size + 1;
  22. }

总结

以上就是 3 种去除有序数组中重复元素的三种算法，其中既有以时间换空间的数组原地操作法，也有空间换时间的普通方法，最后的话则是有一种综合前两种方法优点的方法 - 双指针。通过双指针方法，既能保证空间复杂度为 有序数组去重方法，你会几种？ - 图9#card=math&code=O%281%29&id=Y60jj)，也将时间复杂度限制在了 有序数组去重方法，你会几种？ - 图10#card=math&code=O%28n%29&id=z3XLE)。

想不到连简单的数组去重都有这么大的学问，我们在日常学习时，大多可能只关注于如何实现功能即可。但如果要应用到工作场景中，可能就需要考虑效率问题，此时则需要根据我们的具体需求来进行选择了。

好了，以上就是今天的内容了，如果你还有其他更好的方法，欢迎留言交流呀！