LeetCode:Remove Duplicates from Sorted Array I II

LeetCode:Remove Duplicates from Sorted Array

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 in place with constant memory.

For example,
Given input array A = [1,1,2],

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

分析：从数组的第二个元素开始遍历，把和上一个位置的值不同的的元素保存下来，注意一下n == 0的情形（这里我们直接是inplace操作）

class Solution {
public:
    int removeDuplicates(int arr[], int n) {
        if (n == 0) {arr = NULL;return 0;}
        int index = 1;
        for(int i = 1; i < n; i++)
            if(arr[i] != arr[i-1])
                arr[index++] = arr[i];
        return index;
    }
};

LeetCode:Remove Duplicates from Sorted Array II

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].

分析：和上一题相似，从数组的第三个元素开始遍历，把和前一个的前一个(A[i-2])的值不同的元素保存下来，这里需要注意的是原来的A[i-2]的值可能已经被覆盖了，比如1,1,1,2,2,3遍历到第4个元素2时，需要保存，并且保存在了第三个位置数组变成了1,1,2,2,2,3，遍历到第5个元素2时，前一个的前一个元素本来是1，但是前面已经被2给覆盖了，所有我们需要保存上一次被覆盖元素的索引和值。本文地址

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        //只要当前元素和前一个的前一个不同就保留
        if(n == 0) {A = NULL;return 0;}
        if(n <= 2)return n;
        int index = 2;
        int lastChange, lastChangeIndex = -1; //上一次被覆盖的位置和被覆盖的值
        for(int i = 2; i < n; i++)
        {
            int prepre = A[i-2];
            if(i-2 == lastChangeIndex)prepre = lastChange;//原来的A[i-2]有可能被覆盖了
            if(A[i] != prepre)
            {
                lastChangeIndex = index;
                lastChange = A[index];
                A[index++] = A[i];
            }
        }
        return index;
    }
};

还有一种更优雅的方法是，当我们需要留下某个元素时，先暂时保存好，等到下一轮再覆盖，这样我们找前一个的前一个元素A[i-2]时，就不会出现A[i-2]原来的值被覆盖的情况。

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if(n==0)return 0;
        if(n==1)return 1;
        int num=1,i,temp=A[1];
        for(i=2;i<n;++i)
            if(A[i]!=A[i-2])
            {
                A[num++]=temp;
                temp=A[i];
            }
        A[num++]=temp;
        return num;
    }
};

秒客网

LeetCode:Remove Duplicates from Sorted Array I II

相关文章