26 从排列数组中删除重复项

文|Seraph

1 问题

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。

示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

2 解题

初解：

思路：首先不需要修改数组长度，我这里理解就是将不重复的项往前挪就行，并同时记得有多少个就OK了。
使用两位置计数，一个从前往后循环数据计数；另一个指向当前不重复项的位置。我们这里每次仅需要判断循环计数指针指向的数是否和当前不重复项的数相等，如相等则循环计数指针往下走；如不相等则将该数赋值到下一个当前不重复项的位置，且指向不重复项的位置的指针+1。

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

我们这里要注意用例的边界情况，并做出相应的处理。比如数组为空时，我们应当直接返回0。这种安全性编码虽然完全没有难度，但是我们要非常重视这种情况，因为我们必须考虑所有用例的可能情况，使程序更具健壮性。
结果：耗时处在中偏前。
改进1：添加如下全局作用域代码

static auto x = []{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    return 0;
}();

该代码核心语句为 std::ios::sync_with_stdio(false);,功能是取消cin与stdin的同步。
因为leetcode的环境测试用例是通过cin读取的，如果用例过多或过长，会影响执行速度，这也在我们平常读取文件时，会遇到。
cin一般会慢一些，主要是cin与stdin默认总是保持同步的，也就是两种方法可以混用，而不必担心文件指针混乱。正是因为这个兼容性，导致cin多出许多额外开销。

终解：

static auto x = []{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    return 0;
}();

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

3 积累知识点

1. cin与stdin的同步原因导致读取速度会受影响
2. 重视输入的边界值，特别是空的情况
3. 读取文件是非常耗时的操作，所以一般为了减少耗时，可以将文件之后要用到的数据一次性读取到缓冲区中，然后再从缓冲区中分割需要的数据。而不应该，一次一次读取文件。