leetcode 80. 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.

这个问题的意思很清楚。我在这里用的是遍历解法，可以得到目标数组。这个问题的麻烦是得到目标数组。如果不考虑这一点，用Hashmap遍历一次，然后就可以得到结果了。

代码如下;

public class Solution{    /*     * 这个问题的难点主要在于在原数组的基础上获得目标数组，     * 本题并不难     * */    public int removeDuplicates(int[] nums)     {        if(nums==null || nums.length<=2)            return nums.length;        int count=2,start=2,end=nums.length;        while(start < end)        {            if(nums[start-2]==nums[start-1])            {                if(nums[start]!=nums[start-1])                {                    count++;                    start++;                }                else                {                    //这个问题的难点主要在于在原数组的基础上获得目标数组，                    for(int j=start+1;j<end;j++)                        nums[j-1]=nums[j];                    nums[end-1]=nums[start];                    end--;                }            }else            {                count++;                start++;            }        }        return count;    }}

以下是C++的做法，也就是遍历一次。其实我更喜欢用map做计数。

代码如下：

#include <iostream>#include <vector>using namespace std;class Solution {public:    int removeDuplicates(vector<int>& nums)     {        if (nums.size() <= 2)            return nums.size();        int count = 2;        int begin = 2, end = nums.size();        while (begin < end)        {            if (nums[begin - 2] == nums[begin - 1])            {                if (nums[begin - 1] == nums[begin])                {                    for (int i = begin + 1; i < end; i++)                        nums[i - 1] = nums[i];                    nums[end - 1] = nums[begin];                    end--;                }                else                {                    count++;                    begin++;                }            }            else            {                count++;                begin++;            }        }        return count;    }};