LeetCode经典面试150题-day4（删除有序数组的重复项II）

每天加一句想说的话 ：

坚持分享第四天了，每天一题是学习，也是分享，做算法，秉持的原则是绝对不写超过O(N²)的算法，第一阶段，看懂分析，不看代码也可以根据提示写出正确的方法。😊😊😊

1、题目

2、分析

⑴ 、今天这个问题是对昨天分享的一个提升，删除数组的重复元素，使得重复的元素不超过两次，第一考虑边界问题，考虑数组大小<=2的情况，保证原数组最大只有两个元素，并且重复次数最大为2，所以直接返回原数组的size即可

⑵ 、还是采用双指针的方法，原数组为有序数组，根据题意可知保证数组中重复元素出现的次数不超2即可，有序数组必然是连续的，所以我们可以从第三个元素开始比较，比较nums[0]和nums[2]值是否不同，如果不同则给第三个元素赋nums[2]的值，然后下标加1，index++

⑶ 、根据题意，我们的判断条件就是index - 2，而不是重复1次的index - 1了，最后返回index的值就是新数组的长度了，新数组中每个元素的重复次数都不可能超过两次

3、解题

    /**
     * 删除有序数组中的重复项 II(出现次数超过两次的元素只出现两次)
     *
     * @param nums
     * @return
     */
    public static int removeDuplicates2(int[] nums) {
        int size = nums.length;
        if (size <= 2) {
            return size;
        }
        int slow = 2;
        for (int i = 2; i < size; i++) {
            if (nums[slow - 2] != nums[i]) {
                nums[slow] = nums[i];
                slow++;
            }
        }
        //        while (fast < size) {
        //            if (nums[slow - 2] != nums[fast]) {
        //                nums[slow] = nums[fast];
        //                slow++;
        //            }
        //            fast++;
        //        }
        return slow;
    }

4、复杂度分析

时间复杂度 ：因为只进行了一次遍历就得出了结果，所以时间复杂度是O(n)

空间复杂度 ：因为只创建了一个常数量的数组，所以空间复杂度是O(1)

5、课外分享