Leetcode26. Remove Duplicates from Sorted Array

ddddLeetcode刷题

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

• 快速了解我: About Me

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

Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example:

Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the new length.

首先，是我的代码，基于$C++ 11$新标准编码原则：

//Author: Li-Yingmin@https://liyingmin.wixsite.com/henry
//Email: li_yingmin@outlook.com
//Leetcode-26
//T(n)=O(n), S(n)=O(1)
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(0 == nums.size())
            return 0;
        auto vbeg = nums.begin();
        auto vend = nums.end();
        auto temp = *vbeg;  //若nums为空，执行此操作是未定义的
        ++vbeg;
        for ( ; vbeg != vend; ++vbeg)
        {
            if(*vbeg == temp)
            {
                nums.erase(vbeg);
                --vbeg;
                vend = nums.end();
            }
            else temp = *vbeg;
        }
        return nums.size();
    }
};

主要是使用了STL里的erase()操作来删除元素，有几点需要注意:

• 用erase操作传入指向该元素的迭代器，删除后返回该元素之后的一个迭代器，如果删除的是尾元素，则返回尾后迭代器。
• 若vector是空的，对其执行解引用操作是未定义的行为。
• erase操作之后，被删除元素之前的迭代器是有效的，被删除元素之后的迭代器都会失效，除了返回的迭代器。也就是说，尾后迭代器一定会失效。

优秀代码1：

/*
 * LeetCode, Remove Duplicates from Sorted Array
 * 时间复杂度O(n)，空间复杂度O(1)
 */
class Solution {
public:
    int removeDuplicates( vector<int> & nums )
    {
        if ( nums.empty() )
            return(0);
        int index = 0;
        for ( int i = 1; i < nums.size(); i++ )
        {
            if ( nums[index] != nums[i] )
                nums[++index] = nums[i];
        }
        return(index + 1);
    }
};

• 判断一个vector是否为空，使用empty()函数最好，不要使用0 == v.size()
• 
if ( nums[index] != nums[i] )
nums[++index] = nums[i];

• 上边代码的方式可以适用于有序array前移的操作

优秀代码2：

class Solution {
public:
    int removeDuplicates( vector<int> & nums )
    {
        return(distance( nums.begin(), removeDuplicates( nums.begin(), nums.end(), nums.begin() ) ) );
    }
    template<typename InIt, typename OutIt>//相当于对unique的一种实现方式
    OutIt removeDuplicates( InIt first, InIt last, OutIt output )
    {
        while ( first != last )
        {
            *output++   = *first;
            first       = upper_bound( first, last, *first );
        }
        return(output);
    }
};

• upper_bound(first, last, *first)返回指向第一个比*first大的元素的迭代器，其中，first、last都是迭代器。
• 使用了函数模板，调用时生成对应的实例，InIt实例化为迭代器类型vector<int>::iterator，OutIt也实例化为vector<int>::iterator。
• 前置++与解引用*级别一样，右结合律，后置++级别比*高1级，右结合律
• distance()返回The number of elements between first and last，左闭右开
• 
• 返回的output，就是重排最后一个元素之后的一个迭代器

优秀代码3：使用STL一步完成

class Solution
{
public:
    int removeDuplicates( vector<int> & nums )
    {
        return(distance( nums.begin(), unique( nums.begin(), nums.end() ) ) );
    }
};

• unique()返回不重复重排array的尾后迭代器
•