LeetCode-26-已排序数组去重

问题描述

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

发表评论