在Leetcode的經(jīng)典150題中，有三道從有序數(shù)組中移除重復元素的題目，分別是移除指定元素、移除重復元素、移除重復元素但保留2個重復元素。
27. Remove Element
26. Remove Duplicates from Sorted Array
80. Remove Duplicates from Sorted Array II

不對題目進行追溯，重點對思路進行梳理和總結，并給出示例代碼。

要求

1. 有序數(shù)組
2. 將滿足條件的有效元素移動到數(shù)組的前部，空間復雜度O(1)
3. 返回有效元素數(shù)量

P27 移除指定元素

算法

1. 兩個指針分別指向數(shù)組首尾（left, right）
2. 如果left指針指向為有效元素（不等于val），則向右移動
3. 如果left指針執(zhí)行為無效數(shù)字（等于val），則right指針從尾部向左掃描，找到第一個有效元素，copy到left所指位置，right左移到下一個候選元素。
4. 當right指針移動到left左側，掃描結束，right指向了最后一個有效元素

邊界條件

1. 輸入數(shù)組為空，直接返回0
2. 當left和right指向相同元素時，需要小心處理。如果該元素為有效元素，則left向右移動，此時right指向最后一個有效元素。
3. 如果該元素為無效元素，則right向左移動，有可能越界為負數(shù)，此時數(shù)組中沒有有效元素。在最后返回時，需要特殊處理（直接+1也是可以的，明文處理更容易理解）。

示例代碼

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if (nums.size() == 0)
        {
            return 0;
        }

        int left = 0;
        int right = nums.size() - 1;
        while (left <= right)
        {
            // move to the next val position
            if (nums[left] != val)
            {
                ++left;
                continue;
            }
            // to find next non-val element
            if (nums[right] == val)
            {
                --right;
                continue;
            }
            // copy to left
            nums[left] = nums[right];
            ++left;
            --right;
        }
        return right >= 0 ? right + 1 : 0;
    }
};

P26 移除重復元素

算法

1. 快慢指針（為了和上面保持一致，統(tǒng)一叫做left和right），left 指針始終指向最后一個有效元素，right指向下一個需要處理的元素
2. 如果right指向的元素和left相同，則left保持不動，right向右移動一位
3. 如果right指向的元素和left不同，則將該元素指向left的下一個位置（left向右移動一位）。

邊界條件

• 數(shù)組為空

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

P80 移除重復元素，但是保留2個重復元素

常規(guī)算法
使用一個輔助變量（hitCnt），記錄最近一個有效元素出現(xiàn)的次數(shù)，如果hitCnt大于2，則跳過

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() < 3)
        {
            return nums.size();
        }
        int left = 0;
        int right = 1;
        int hitCnt = 0;
        for (; right < nums.size(); ++right)
        {
            if (nums[left] != nums[right])
            {
                nums[++left] = nums[right];
                hitCnt = 0;
                continue;
            }
            ++hitCnt;
            if (hitCnt < 2)
            {
                nums[++left] = nums[right];
            }
        }
        return left + 1;
    }
};

更優(yōu)算法（通用）
比較當前處理元素與有效元素中的倒數(shù)第2個元素（left - 1 指向的元素），如果相等，則跳過，如果不等于，則拷貝到有效元素中。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() < 3)
        {
            return nums.size();
        }
        int left = 1;
        int right = 2;
        while (right < nums.size())
        {
            if (nums[right] != nums[left - 1])
            {
                nums[++left] = nums[right];
            }
            ++right;
        }
        return left + 1;
    }
};