pic

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

分析

题目的意思是，给定一个排序的整数数组，在数组中去除重复的元素，使原数组所有元素都仅出现1次，并返回元素的个数.

    *题目已经要求不能使用额外空间，所以借助堆栈和其他数组的方法都不可行。
    *设置两个指针，一个负责遍历输入数组的每个元素，一个指向去重后数组的元素。

Code

class Solution {
public:
    /* 
     * 设置两个指针，一个指针负责遍历输入数组所有pos，一个指针负责指向去重后的数组pos
     *
     * */
    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( !A || n <= 0)
            return 0;
        int ret = 1;
        int i = 0; 
        int j = i + 1; 
        while( j < n )
        {
            if( A[i] == A[j])
                j++;
            else
            {
                ret++;
                // 给去重后的数组元素赋值
                A[i + 1] = A[j];
                i++, j++;
            }

        }
        return ret;
    }
};

pic