删除排序数组中的重复项 II 题目

给定一个增序排列数组 nums ，你需要在 原地 删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。(来源LeetCode 80)

例子

示例1

输入：nums = [1,1,1,2,2,3]

输出：5, nums = [1,1,2,2,3]

示例2

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]

示例3

输入：nums = [1,1,1,1]

输出：2, nums = [1,1]

解题思路

这道题目其实是前面我们有聊过的“删除排序数组中的重复项“的进阶版，其实我们直接的思路大体相似，无非这道题目是使每个元素最多出现两次，当然代码实现上会稍微复杂一些，注意的条件也比较多。

思路一：我们还是遍历数组，我们可以从第三个元素开始遍历，当nums[i]==nums[i-2]时，即这三个元素完全相等时，我们可以往后面找，找到一个和nums[i]不相同的元素为止，将这后面这一串往前挪，这里就要注意不同情况，当往后找的过程中如果找不到，那就应该直接返回i，例如nums=[1,1,1,1,1];如果找到了，我们移动的的时候也要注意，我们先定义个变量标记移动了多少位，然后进行赋值，赋值完后“数组的长度”其实也是分两种情况的，例如nums=[1,1,1,1,1,2,3,4,5],我们移动后变成nums={1,1,2,3,4,5,3,4,5},但是我们应该只取前6位，例如nums={1,1,1,1,1,2},我们移动后变成nums={1,1,2,1,1,2},但是我们应该只取前2位；这就是两只不同情况，具体大家可以结合下面图示和代码仔细揣摩一下。所以我们移动完后，要改变遍历的数组长度，直至遍历结束，i就是需要返回的数组长度。

思路二：上述我们其实貌似不用这么复杂，我们定义两个指针n,i，一个负责往后遍历，一个记录当前“新数组“需要存放的最新位置，当往后遍历的过程中发现当索引下标的值不等于前面第二个元素时，则将数组记录需要存放的最新位置设置成当前元素,以此类推返回i即为数组长度，大家可以结合如下代码仔细思考一下，再尝试着自己去实现。

删除排序数组中的重复项

MR.Zhu，公众号：1024和996删除排序数组中的重复项

代码实现

/** * leetcode 80 */public class Solution {    /**     * 方法一     *     * @param nums     * @return     */    public int removeDuplicates(int[] nums) {        if (nums == null || nums.length == 0) {            return 0;        }        if (nums.length < 3) {            return nums.length;        }        int i = 2;        int length = nums.length;        while (i < length) {            if (nums[i] == nums[i - 2]) {                int flag = i;                int point = i;                while (point + 1 != length && nums[point] == nums[point + 1]) {                    point++;                }                //没找到，则返回                if (point + 1 == length) {                    return i;                }                //移动赋值                for (int j = point + 1, k = 0; j < length; j++, k++) {                    nums[flag + k] = nums[j];                }                //判断有效长度                if (length - point - 1 < point - i) {                    length = i + (length - point - 1);                } else {                    length = length - (point + 1 - i);                }            }            i++;        }        return i;    }    /**     * 方法二     * @param nums     * @return     */    public int removeDuplicates2(int[] nums) {        int i=0;        for(int n:nums){            if(i<2){                i++;                continue;            }            if(n!=nums[i-2]){                nums[i]=n;                i++;            }        }        return i;    }    public static void printArr(int[] arr) {        for (int num : arr) {            System.out.print(num + "\t");        }        System.out.println();    }    public static void main(String[] args) {        int nums[] = { 0, 1, 1, 1, 1, 2, 3, 3, 3, 4 };        System.out.println("方法一删除重复项后数组长度:" + new Solution().removeDuplicates(nums));        System.out.println("方法一删除重复项后数组为:");        printArr(nums);        int nums2[] = { 0, 1, 1, 1, 1, 2, 3, 3, 3, 4 };        System.out.println("方法二删除重复项后数组长度:" + new Solution().removeDuplicates2(nums2));        System.out.println("方法二删除重复项后数组为:");        printArr(nums2);           }}

运行结果