Leetcode80. Remove Duplicates from Sorted Array II

ddddLeetcode刷题

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

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.

我的代码：

//Author: Li-Yingmin@https://liyingmin.wixsite.com/henry
//Email: li_yingmin@outlook.com
//Leetcode-80
//T(n)=O(n), S(n)=O(1)
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty()) return 0;
        unsigned cnt = 0;
        int temp = nums[0];
        vector<int>::size_type index = 1;//decltype(nums.size()) index = 0;
        for(decltype(nums.size()) i = 1; i < nums.size(); i++)
        {
            if(nums[i] != temp)
            {
                cnt = 0;
                temp = nums[i];
                nums[index++] = nums[i];
            }
            else
            {
                ++cnt;
                if(cnt < 2)
                {
                    nums[index++] = nums[i];
                }
            }
        }
        return index;    
    }
};

• 对于顺序容器的下标索引，比如String，vector，都是用vector<int>::size_type，这样才是大气的写法。
• 可以用简单的写法，decltype(nums.size())，表示上述类型

优秀代码1：

class Solution
{
public:
    int removeDuplicates(vector<int>& nums)
    {
        const int n = nums.size();
        int index = 0;
        for (int i = 0; i < n; ++i)
            {
                if (i > 0 && i < n - 1 && nums[i] == nums[i - 1] && nums[i] == nums[i + 1])
                    continue;
                nums[index++] = nums[i];
            }
        return index;
    }
};

• 利用nums[i] == nums[i-1] && nums[i] == nums[i+1]来精妙的判断是否应该剔除这个元素。是从中间剥除多余元素。
• 一定要注意这里nums[i] == nums[i-1] && nums[i] == nums[i+1]是否对于现在的nums仍然是准确的，由于原来的nums经过了修改，见下一优秀代码分析！
• if条件显得有点繁琐，可以把一些东西放到循环条件里：

优秀代码2：

class Solution
{
public:
    int removeDuplicates(vector<int>& nums)
    {
        if (nums.size() <= 2) return nums.size();
        int index = 2;
        for (int i = 2; i < nums.size(); i++)
            {
                if (nums[i] != nums[index - 2])//这里不能用nums[i - 2]
                    nums[index++] = nums[i];
            }
        return index;
    }
};

• 这种写法可能会想当然的认为是nums[i - 2] != nums[i]，但实际上是错误的！
• 
• 为什么要使用nums[i] != nums[index - 2]？因为我希望和原nums进行对比，而不是现在的临时nums做对比，但是由于是in-place操作，所以原来的nums已经不在了；只能使用index-2来等效。
• 当对一个容器进行in-place修改时，一定要小心：现在的nums和原来的nums已经不一样了！