Remove Duplicates from Sorted Array

 

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


Naive Way:直观的可以在遍历的时候keep一个同样大小的数组来记录每个数是否出现过，然后第二次遍历将数进行移动， 或者说再简历一个新数组。这样的做法有点不动脑。应该算是最naive的方法。但是直观觉得很可行。

Improved Way:题目既然要求了constant memory，那么这是一个big hint，说明我们可以不借助多余数组完成remove。比较直觉的是这种在数组上处理数据的，应该可以通过keep 指针来帮助记录关键位置来实现。文章最后有其他类似题目的链接。

//这是我第二次做的代码，两个指针记录有效的部分和下一个可能的数的位置。

    public int removeDuplicates(int[] A) {
        int p1 = 0;
        int p2 = 0;
        int begin, end;
        if(A.length==0){return 0;}
        // points p2 to a next element;
        while(p2 < A.length){
            if(A[p1]!=A[p2])
                break;
            p2++;
        }
        end = p2;
       
        // set p1 ~ end
        begin = p1+1;
        while(begin < end && p2 < A.length){
            if(A[begin]==A[p1]){
                A[begin] = A[p2];
                // shift p2
                int temp = A[p2];
                while(p2 < A.length){
                    if(A[p2] != temp)
                        break;
                    p2++;
                }
            }else{
                p1 = begin;
            }
            begin++;
        }
       
        // set the rest according to p2
        while(p2 < A.length){
            A[begin++] = A[p2];
            int temp = A[p2];
            while(p2 < A.length){
                if(A[p2] != temp)
                    break;
                p2++;
            }
        }
       
        return begin;
    }



//这是我第一次写得代码，思想更简单，坚信两个指针足矣。（居然如此简洁，难道在后退，日）

public int removeDuplicates(int[] A) {
        if(A.length == 0){return 0;}
        int i, j;
        i = 1;
        j = 0;
        while(i < A.length){
            if(A[i] == A[j]){
                i++;
            }else{
                A[++j]=A[i++];
            }
        }
        return j+1;
    }

类似的要求在constant space的情况下完成对数组的处理的题目还有