题目

删除有序数组中的重复项

思路

常规

分步骤解决

1. 去除重复值
2. 移动数组，保持数据相对位置(通过另一个数组的辅助将原合规的数据移动）

 public int removeDuplicates(int[] nums) {
        // 去重
        // 根据长度赋值，找到有效数字的长度，然后创建新数组返回k
        if (nums == null || nums.length == 0) return 0;
        int count = removeDup(nums);
        mvNonDup(nums, count);
        return count;
    }

    /**
      找到重复值并设置
      */
    int removeDup(int[] nums) {
        int k = 0;
        // 临时数标识
        int temp = Integer.MIN_VALUE;
        int total = nums.length;
        //  *优化点*
        for(int i = 0; i < total; i ++) {
            if (nums[i] != temp) {
                // 重新赋值
                temp = nums[i];
                k++;
            } else {
                nums[i] = Integer.MIN_VALUE; // 重复值（不合规数字）设置特殊值
            }
        }
        return k;
    }

    /**
      移动非重复值到新的位置
      */
    void mvNonDup(int[] nums, int total) {
        int[] copy = new int[total];
        int k = 0;
        int len = nums.length;

        for(int i = 0; i < len ; i++) {
            // 判断是否是置空
            if (nums[i] != Integer.MIN_VALUE) {
                copy[k] = nums[i];
                k ++;
            }
        }

        // 讲整理出来的值重新赋值回
        for(int i = 0; i < total; i ++) {
            nums[i] = copy[i];
        }

    }

快慢指针

1. 快慢指针，慢指针指向最新的合规数据位置
2. 快指针指向当前处理的数字
3. 当快指针指向的数字不和最后一个合规数字相同，表明是新的合规数字；添加到下一个合规数位置

    
    public int removeDuplicates(int[] nums) {
	// 入参边界值处理 
        if (nums == null || nums.length == 0) return 0;
        int count = removeDup(nums);
        return count;
    }

    /**
      移除重复值
      用双指针
      */
    int removeDup(int[] nums) {
        // 指向最后一个有效位
        int slow = 0;
        int total = nums.length;
        for(int i = 0; i < total; i ++) {
            if (nums[i] != nums[slow]) {
                // 找到合规数字，合规位置移动+1；并移动合规数字
                slow++;
                nums[slow] = nums[i]; 
            } 
        }
        // slow从0开始计算 
        return slow + 1;
    }

Q.E.D.