Remove Duplicates from Sorted Array

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length

这个问题比较简单,如果用straight forward想法,每个元素剔除之后整个数组往前移动,那么会造成O(n^2)的时间复杂度。

因为我们不介意输出长度的内容,所以我们可以用两个指针,一个从头开始增加,一个从尾开始减少,从头的指针发现一个和element相同的数,那么从尾部找出一个和element不相同的数将其替换即可,这样当头和尾两个指针相遇得到的就是新的array了。

有一些细节需要注意的是
1.输出的是长度,记得在index的基础上+1
2.结束条件是头和尾相遇时 start <= end 这时候保证从相遇end之后的都是和element相同的数了。如果start = end,还是会进入循环计算一遍,如果相等,那么end会继续减一,end这时候已经小于start,这时直接输出end + 1为长度即可。

public class Solution {
    public int removeElement(int[] A, int elem) {
        if (A.length == 0)
            return 0;
        else
        {
            int end = A.length-1;
            int start = 0;
          
            while(start <= end)
            {
                if (A[start] == elem)
                {
                    if (A[end] != elem) // find an element from the end of the array and replace
                    {
                        A[start] = A[end];
                        start++;
                        end--;
                    }
                    else
                    {
                        end--;
                    }
                }
                else
                {
                    start++;
                }
            }
            return end + 1;
        }
       
    }
}

跟进问题和类似问题:

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.

用一个counter来计算需要删除多少个数,从头到尾扫描一遍数列,当发现重复的数以后,counter++,如果不同,则把当前数A[i] copy到 A[i-counter]的位置,最后的数列就是A[i-counter], 长度就是原来数列的长度-counter,代码非常简洁,其实同样的代码用在上题会使上题更简单。i是当前正在扫描的数,而i-counter就是当前的已经处理好了的array的结尾。

public class Solution {
    public int removeDuplicates(int[] A) {
        int len = A.length; // the length of the new array
        if (A.length == 0 || A.length == 1) // if 0 or 1 element, no duplicate
            return len;
        else
        {
            int count = 0;
            for (int i = 1; i < A.length; i++)
            {
                if (A[i] == A[i-1])
                {
                    count++;
                }
                else if (count > 0) // if exist duplicate elment to replace
                {
                    A[i-count] = A[i];
                }
            }
            return A.length - count;
        }
    }
}

如果不是删除所有相同的数,而是允许一个数最多出现两遍呢?
如果直接把判断条件改成A[i] == A[i-1] && A[i] == A[i-2],会出问题,为什么呢,因为在上题中A[i]和A[i-1]是相邻的,每当i++以后,原来的A[i](或者说现在的A[i-1])是不可能已经被替换了的,但是如果是A[i-2]的话,是有可能已经被新数据替换了的。例如1112233, 当运行过第三个1时,1会被替换成2,于是数据变成1122233,当再扫到第二个2时,程序就误以为这个二和前面的相等,count++(而实际上count不应该++,因为2只有两个)。

所以我们不应该直接比较A[i],而应该拿当前数据和新array里面的数据比较,和上题一样,i-counter – 1是当前已经处理好了的array的最后一位,而i-counter-2是倒数第二位。所以是用当前正在扫描的数A[i]和A[i-counter-1]和A[i-counter-2]来比较,于是代码就变成

public class Solution {
    public int removeDuplicates(int[] A) {
        if (A.length == 0 || A.length == 1 || A.length == 2) // if 0 or 1 element, no duplicate
            return A.length;
        else
        {
            int count = 0;
            for (int i = 2; i < A.length; i++)
            {
                if (A[i] == A[i-count-1] && A[i-count-2])
                {
                    count++;
                }
                else if (count > 0) // if exist duplicate elment to replace
                {
                    A[i-count] = A[i];
                }
            }
            return A.length - count;
        }
    }
}

Second Submission:

Use an end pointer to keep track of the new array. notice the array scan start from 1 (1 elements will have no duplicate)

public class Solution {
    public int removeDuplicates(int[] A) {
        if (A.length == 0 || A.length == 1) // if 0 or 1 element, no duplicate
            return A.length;
        int end = 1;
        for (int i = 1; i < A.length; i++) {
            if (A[i] != A[end - 1]) {
                if (i != end) {
                    A[end] = A[i];
                }
                end++;
            }
        }
        return end;
    }
}

Simplest code, include condition of 0 and 1

public class Solution {
    public int removeDuplicates(int[] A) {
        int p = -1;
        for (int i = 0; i < A.length; i++) {
            if (p == -1 || A[i] != A[p]) {
                p++;
                A[p] = A[i];
            }
        }
        return p+1;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s