(每日算法)LeetCode --- Remove Duplicates from Sorted Array II (刪除重復元素II)

Remove Duplicates from Sorted Array II

Leetcode

題目：

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

給定一個有序表，每個元素最多出現兩次。刪除掉多余的元素，返回剩余元素的個數。

思路：

兩個指針，一個指向合法位置的下一個位置 （index） ，另一個用於遍歷元素 (i) 。兩個指針之間的是無效元素。

這個時候判斷 i 指向的元素和 index - 2 指向的元素是否相同。

代碼如下：

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        int deleted = 0; //已經刪除的元素個數
        if(n < 3)        //最多含有2個元素，一定滿足題意
            return n;
        int index = 2; //可能不合法的位置
        for(int i = 2; i < n; i++)
        {
            if(A[i] != A[index - 2] )
                A[index++] = A[i];
        }
        return index;
    }
};