LeetCode-26-已排序数组去重

LeetCode-26-已排序数组去重

Apr 27, 2019
Coding
Algorithm, LeetCode

问题描述 #

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;