leetcode: Remove Duplicates from Sorted Array II

问题描述：

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

原问题链接：https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

 

问题分析

初始方法

　　这是一个比较容易想到的办法，就是既然每个元素只允许出现两次，我们可以用一个map来记录每个元素出现的次数。同时用一个计数器来统计所有出现的合法的字符。在遍历整个列表的时候，判断每个元素，如果这个元素不在这个map里，则统计数coun++，并将这个值和对应的出现次数1加入到map中。如果map里有这个元素，但是出现的次数小于2，则count++，并将对应的出现次数加1。这里需要对元素做一个交换的操作，保证最后元素的顺序符合要求。

　　详细的实现如下：

 

public class Solution {
    public int removeDuplicates(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int count = 0;
        for(int i = 0; i < nums.length; i++) {
            int item = nums[i];
            if(map.containsKey(item)) {
                if(map.get(item) < 2) {
                    map.put(item, map.get(item) + 1);
                    swap(nums, count++, i);
                }
            } else {
                map.put(item, 1);
                swap(nums, count++, i);
            }
        }
        return count;
    }
    
    private void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

　　这种思路比较容易想到，但是由于里面有大量的类型boxing, unboxing，所以它的执行效率受到比较大的影响。 

 

改进方法

　　实际上如果仔细分析问题描述中的要求，我们还有一些地方没有利用上。比如说它里面给定的元素都是排序的。这是一个非常有用的地方。既然都是排序的，那么我们不用费劲去用一个map来保存元素了。只要从头往后遍历的时候去看这个元素，如果它当前的值比它索引之前两个位置的元素大，那么说明这个元素和前面的不同，需要将它加入到数组前面去。我们用一个变量i来表示符合条件的元素的索引。同时，针对数组长度的情况，要考虑当前索引小于2的边界情况。

　　这种实现更加简单高效，详细的代码实现如下：

 

public class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for (int n : nums)
            if (i < 2 || n > nums[i - 2])
                nums[i++] = n;
        return i;
    }
}