问题描述

LeetCode – Remove Duplicates from Sorted Array
对已经排好序的数组，去除其中重复的元素，并返回去重后的长度如[1,2,2,3,3]，去重后为[1,2,3] ，去重后长度为3

算法1

两个指针，前者(p)记录当前去重后的最后一个元素，后者(i)不断遍历数组，寻找新元素。

int removeDuplicates(int* nums, int numsSize){
    if(numsSize == 0) return 0;

    int p = 0; // 指向当前去重后数组的最后一个元素，初始为0位置

    for(int i = 1; i < numsSize; i++){
        // 发现新的元素，放到p+1位置
        if( nums[i] != nums[p]) {
            p ++;
            nums[p] = nums[i];
        }
    }

    return p + 1;
}

算法2

来自Discuss区

遍历数组，使用count记录当前出现了多少次重复
如果出现重复，则count++
如果没有重复，则把当前的元素 i 放到它在去重后数组的位置 i-count处

int count = 0;
for(int i = 1; i < n; i++){
    if(A[i] == A[i-1]) count++;
    else A[i-count] = A[i];
}
return n-count;

作者：JarvisChu
原文链接：LeetCode-26-已排序数组去重
版权声明：自由转载-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 3.0