1、地址

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

2、题面分析

题目

image.png

题目信息

  • 所有对数值的操作都需要最终在nums上
  • 返回的整数len，表名nums[0, len-1]的部分是答案
  • 超出的部分[len, nums.length -1]是可以用来做草稿的
  • 2、删除有序数组中的重复项 - 图2 的空间意味着我们只能设定常数个变量。

3、双指针 O(N)

求解思路

  • 确定每一个需要的数
    • 数组从小到大排序，通过前后比较可以确定每一个需要的数的位置
  • 统计需要的数
    • 没发现一个需要的数，统计值加一
  • 移动需要的数
    • 将需要的数移动到数组的最左边（需要的数的最右边）

TIPS：使用两个指针，第一个指针指向最后一个需要的数，第二个指针指向已经变了的数，直到遍历完成。
每次移动需要的数，第一个指针向后移动一位

代码实现

  1. class Solution {
  2.     public int removeDuplicates(int[] nums) {
  3.         int len = nums.length;
  4.         if(len < 2){
  5.             return len;
  6.         }
  7.         int firstIndex = 0;
  8.         int curIndex = 1;
  9.         while(curIndex < len){
  10.             int firstIndexNum = nums[firstIndex];
  11.             int curNum = nums[curIndex];
  12.             if(firstIndexNum != curNum){
  13.                 if(firstIndex < curIndex - 1){
  14.                     nums[++firstIndex] = nums[curIndex];
  15.                     curIndex++;
  16.                 }else{
  17.                     curIndex++;
  18.                     firstIndex++;
  19.                 }
  20.             }else{
  21.                 curIndex++;
  22.             }
  23.         }
  24.         return firstIndex + 1;
  25.     }
  26. }

时间复杂度

计算 O(N)
空间 O(1)

总结

如果算法要求使用常数的额外空间进行求解，一般可以尝试在输入的变量中找到额外操作空间

4、位标记法(不推荐)

求解思路

  • 不考虑O(1)的空间限制
  • 标记每一个需要的数的下标

  • 是否有一个非常省内存的方式完成标记 BitSet

    代码实现

    1. class Solution {
    2.   public int removeDuplicates(int[] nums) {
    3.       int len = nums.length;
    4.       if(len < 2){
    5.           return len;
    6.       }
    7.       BitSet indexSet = new BitSet();
    8.       indexSet.set(0);
    9.       for(int i = 1; i < len; i++){
    10.           if(nums[i] != nums[i-1]){
    11.               indexSet.set(i);
    12.           }
    13.       }
    14.       int retLen = 0;
    15.       for(int i = 0; i < len; i ++){
    16.           if(indexSet.get(i)){
    17.               nums[retLen++] = nums[i];
    18.           }
    19.       }
    20.       return retLen;
    21.   }
    22. }

    时间复杂度

  • O(N)但是比双指针复杂度要高，而且空间不是O(1)

    总结

    不推荐用这个方法，使用了两次循环遍历，而且使用了额外空间。只做参考使用，提供额外的解题思路