删除有序数组中的重复项（C Language）

题目

26. 删除有序数组中的重复项 - 力扣（Leetcode）https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

思路1：暴力求解

这个题目暴力的解法就是找到重复项，多次挪动数据覆盖删除。通过两层循环，外层循环遍历数组元素，内层循环更新数组。

很明显暴力解法的时间复杂度是，这道题目暴力解法在LeetCode上是可以过的。 

int removeDuplicates(int* nums, int numsSize)
{
    if (numsSize == 0)
    {
        return 0;
    }
    int i = 0;
    while (i < numsSize - 1)
    {
        if (nums[i] == nums[i + 1])
        {
            for (int j = i + 1; j < numsSize - 1; ++j)
            {
                nums[j] = nums[j + 1];
            }
            --numsSize;
        }
        else
        {
            ++i;
        }
    }
    return i + 1;
}

思路2：开辟额外的数组

开辟一个临时数组，依次遍历nums数组，把相同的值合成一个数tmp数组中，再把tmp的值拷贝回去。此时时间复杂度为，但是空间复杂度也为，经典的空间换时间。

但是该解法不满足题目空间复杂度为的条件。

int removeDuplicates(int* nums, int numsSize)
{
    if (numsSize == 0)
    {
        return 0;
    }
    int* tmp = (int*)malloc(sizeof(int) * numsSize);
    tmp[0] = nums[0];
    int size = 1;
    for (int i = 1; i < numsSize; ++i)
    {
        if (nums[i] != tmp[size - 1])
        {
            tmp[size] = nums[i];
            ++size;
        }
    }
    for (int j = 0; j < size; ++j)
    {
        nums[j] = tmp[j];
    }
    free(tmp);
    tmp = NULL;
    return size;
}

思路3：双指针

首先注意数组是有序的，那么重复的元素一定会相邻。其次题目要求删除重复元素，实际上就是将不重复的元素移到数组的左侧。

考虑用2个指针，一个在前记作left，一个在后记作right，比较left和right位置的元素是否相等。

如果相等，right后移1位；如果不相等，将right位置的元素复制到left+1位置上，left后移1位，right后移1位。

重复上述过程，直到right等于数组长度。

返回left+1，即为新数组长度。

int removeDuplicates(int* nums, int numsSize)
{
    if (numsSize == 0)
    {
        return 0;
    }
    int left = 0;
    int right = 1;
    while (right < numsSize)
    {
        if (nums[right] != nums[left])
        {
            nums[left + 1] = nums[right];
            left++;
            right++;
        }
        else
        {
            right++;
        }
    }
    return left + 1;
}

思路4：三指针

三指针是在双指针的基础上改进的，便于理解。

设立三个指针，一个指针dst指向下一个将要赋值的位置，另外两个指针left、right指向重复项的区间范围。

int removeDuplicates(int* nums, int numsSize)
{
    if (numsSize == 0)
    {
        return 0;
    }
    int dst = 0;
    int left = 0;
    int right = 1;
    while (right < numsSize)
    {
        if (nums[right] == nums[left])
        {
            ++right;
        }
        else
        {
            nums[dst] = nums[left];
            ++dst;
            left = right;
            ++right;
        }
    }
    nums[dst] = nums[left];
    ++dst;
    return dst;
}