排序数组中剔除重复元素 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:先把重复元素置为‘\0’,只留一个,然后再把后面的元素填充到前面’\0′位置

方法2:遍历一次,直接把后面元素填充到前面

字符串以\0结尾,用方法1,数组重复数置0,也会导致数组中原本就有0的情况消失。

方法2是最好的。

 

public class RemoveDuplicatesFromSortedArray {
    //扫描两遍,先将重复的元素只留一个,其他置为'\0';再用后面的元素填充前面的置'\0'位;时间复杂度o(n+n)
    public int removeDuplicates1(int[] A) {

        int count = A.length;
        if (count == 0 || count == 1) return count;
        int pre = 0;
        for (int i = 1; i < count; i++, pre++) {
            if (A[pre] == A[i]) {
                A[pre] = '\0';
            }
        }
        for (int i = 0; i < A.length; i++) {
            if (A[i] == '\0') {
                for (int j = i; j < A.length; j++) {
                    if (A[j] != '\0') {
                        A[i] = A[j];
                        A[j] = '\0';
                        break;
                    }
                }
            }
        }
        return A.length;
    }

/*扫描一遍进行压缩 直接拿后面的元素填充前面的元素 1 1 2 2 4 4 4 6   */

    public int removeDuplicates2(int[] A) {
        int i = 0;
        for (int j = i + 1; j < A.length; ) {
            if (A[i] == A[j]) {
                j++;
            } else {
                A[++i] = A[j];
            }
        }
    return i+1;
    }
}
Tagged on: , ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>