Leetcode 80

题目要求

有序数组nums，原地删除其中出现次数超过2次的元素的超过部分（即保证每个元素至多出现两次），并返回删除后的新长度

核心算法和原理

• 颇有「内存压缩」的意味。考虑双指针，一个指向当前遍历的元素 (i)，一个指向新数组的末尾(stackSize)

• 为什么说这是个Stack？可以把新数组当成一个栈，每次遍历时拿nums[i] 和 栈顶下面的元素比较；如果不同则入栈

代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() < 2) return nums.size();
        int stackSize = 1, n = nums.size();
        for (int i = 2; i < n; i++ ) {
            if (nums[stackSize - 1] != nums[i]) {
                nums[++stackSize] = nums[i];
            }
        }   
        return stackSize + 1;
    }
};