LeetCode刷题：26. 删除有序数组中的重复项

文章目录

写在前面
⭐️26. 删除有序数组中的重复项⭐️
- 🔐题目描述
- 💡解题思路
- 🔑代码

写在前面

本题的题解代码是用C语言编写的。

📒博客主页：2023Fighting的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由2023Fighting原创，CSDN首发！
📆首发时间：🌴2023年10月22日🌴
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
🙏文章仅供参考，如果发现错误，请及时告知我哦！感谢感谢！

题目链接：26. 删除有序数组中的重复项

⭐️26. 删除有序数组中的重复项⭐️

🔐题目描述

给你一个 非严格递增排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_ ]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ，并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

💡解题思路

思路一：空间换时间。（开辟额外空间了不符合题目要求，仅供参考）
首先注意数组是有序的，那么重复的元素一定会相邻。删除重复元素，实际上就是将不重复的元素拷贝到新开辟的空间中去，然后再拷贝回原数组即可。
这里使用 3 个指针，两个指针指向原数组，一个在前记作 src2，一个在后记作 src1，另一个指针指向新开辟的空间，记作 dest。算法流程如下：

开辟一块和原数组大小一样的空间。
比较 src1 和 src2 位置的元素是否相等。
如果相等，src2 后移 1 位，如果不相等，将 src1 位置的元素复制到 dest 位置上，dest 后移一位，src1 移动到 src2 位置上，src2 后移一位，重复上述过程，直到 src2 等于数组长度。出了循环以后再把 src1位置的数据拷贝到 dest位置上，dest 后移一位。
将数据拷贝回原数组。
返回 dest，即为新数组长度。

图解如下：
在这里插入图片描述
最后再把 tmp数组的内容拷贝到nums，拷贝完成后，释放 tmp指向的空间。

思路二：双指针。
上一种思路，开辟了额外的空间，不符合题意，因此我们直接在原数组动手。
这种思路实际上是把不重复的元素全部移动到数组的左边。
该思路使用了两个指针，一个在前记作 src, 一个在后记作 dest。算法流程如下：

比较 dest 和 src位置上的元素是否相等。
如果相等，src 后移一位；如果不相等，dest 后移一位，将 src 位置的元素拷贝到 dest，src后移一位，重复上述过程，直到 src 等于数组长度。
返回 dest + 1，即为新数组长度。

图解如下：
在这里插入图片描述

🔑代码

思路一：空间换时间。

int removeDuplicates(int* nums, int numsSize)
{
	//开辟tmp数组
	int* tmp = (int*)malloc(sizeof(int) *numsSize);
    int src1 = 0;
    int src2 = 1;
    int dest = 0;
    //往tmp数组中拷贝数据
    while (src2 < numsSize)
    {
        if (nums[src1] == nums[src2])
        {
            src2++;
        }
        else
        {
            tmp[dest++] = nums[src1];
            src1 = src2;
            src2++;
        }
    }
    tmp[dest++] = nums[src1];
    //拷贝回原数组
    for (int i = 0; i < dest; ++i)
    {
        nums[i] = tmp[i];
    }
   free(tmp);
   return dest;
}

思路二：双指针。

int removeDuplicates(int* nums, int numsSize)
{
    int src = 1;
    int dest = 0;

    while (src < numsSize)
    {
       if (nums[src] == nums[dest])
       {
           src++;
       }
       else
       {
           nums[++dest] = nums[src++];
       }
    }
    return dest + 1;
}