80. 删除有序数组中的重复项II

双指针法

class Solution {
    public int removeDuplicates(int[] nums) {

        /**
         * 双指针遍历数组
         * 定义一个flag来指示重复元素出现的次数
         */
        int n = 0;
        int flag = 0;

        for (int i = 1; i < nums.length; i++) {

            if (nums[n] < nums[i]){

                n++;

                if (i != n) {
                    nums[n] = nums[i];
                }

                flag = 0;
            }

            /**
             * flag等于0时进入该判断，说明元素刚好重复了两次
             * 此时累计flag，n的下一个元素肯定需要被覆盖
             */
            else if (flag < 1){

                flag++;
                n++;
                nums[n] = nums[i];
            }

            /**
             * 如果重复次数超过2，就让i一直往前遍历
             */
            else if (flag == 1){
                continue;
            }
        }

        return n + 1;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

优化1——以2为间隔进行判断

class Solution {
    public int removeDuplicates(int[] nums) {

        /**
         * 双指针遍历数组，数组长度小于等于2时不用处理
         * 当前元素i大于n - 2时说明重复次数小于等于2
         */
        if (nums.length <= 2){
            return nums.length;
        }

        int n = 2;

        for (int i = 2; i < nums.length; i++) {

            if (nums[n - 2] < nums[i]){

                if (n != i) {
                    nums[n] = nums[i];
                }
                
                n++;
            }
        }

        return n;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

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