数据结构C++｜实例：LeetCode26—删除排序数组中的重复项（附视频）金鳞岂是池中物全集下载,重生之千金毒妃,五年级数学上册教案,

数据结构C++｜实例：LeetCode26—删除排序数组中的重复项（附视频）

2022-06-26
John Dowson

合作将帮助宁德时代锁定钴资源据媒体消息，洛阳钼业、宁德时代将联合开发Kisanfu铜钴矿项目。此外，双方还有意在镍、锂资源开发扩大合作，在新能源金属资源领域建立全方面战略合作伙伴关金鳞岂是池中物全集下载,重生之千金毒妃,五年级数学上册教案,

本文摘自《数据结构在线编程实训（C++语言）（全程视频讲解版）》

【实战2.1】LeetCode26—

删除排序数组中的重复项

问题描述：给定一个排序数组（选择C语言编译环境时用数组nums[0..numsSize-1]存放该有序序列），你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，即算法的空间复杂度为O(1)。例如，给定数组nums=[1，1，2]，函数应该返回新的长度2，并且原数组nums的前两个元素被修改为1，2，不需要考虑数组中超出新长度后面的元素。要求设计满足题目条件的如下函数：

classSolution{

public:

intremoveDuplicates(int*nums, intnumsSize)

{ … }

};

解：由于nums是有序数组，重复的元素移动是相邻的，利用《教程》第2章例2.3的前面两种解法思路，采用解法1的整体建表法时，先在结果数组nums中存放第一个元素，k表示保留的元素个数，初始时置为1。用i遍历其他元素，若nums[i]=nums[k-1]（nums[k-1]为结果数组中的尾元素）表示nums[i]是重复元素，否则为保留元素，将其插入时nums[k]中，置k++。最后返回保留的元素个数k。对应的代码如下：

classSolution{

public:

intremoveDuplicates(int*nums, intnumsSize)

{ if(numsSize== 0|| numsSize== 1)

returnnumsSize; //长度为0或者1的情况

intk= 1;

for( inti= 1;i<numsSize;i++)

if(nums[i]!=nums[k -1]) //将不重复的元素插入到nums中

{ nums[k]=nums[i];

k++;

}

returnk; //返回新的长度

}

};

上述程序的运行时间为20ms，占用空间为8MB，编译语言为C++。

采用《教程》第2章例2.3解法2的元素移动法时，用k累计重复的要删除的元素个数，初始为0，同样先在结果数组nums中存放第一个元素。用i遍历其他元素，若nums[i]=nums[i-1]表示nums[i]是重复元素，置k++，否则为保留元素，将其前移k个位置。最后返回保留的元素个数numsSize-k。对应的代码如下：

classSolution{

public:

intremoveDuplicates(int*nums,intnumsSize)

{ if(numsSize== 0|| numsSize== 1)

returnnumsSize; //长度为0或者1的情况

intk= 0; //累计要删除的元素个数

for( inti= 1;i<numsSize;i++)

if(nums[i]!=nums[i -1]) //将要保留的元素前移k个位置

nums[i-k]=nums[i];

else//累计删除的元素个数k

k++;

returnnumsSize-k; //返回新的长度

}

};

上述程序是AC代码，运行时间为24ms，占用空间为8.1MB，编译语言为C++。

视频讲解

参考书籍

《数据结构在线编程实训（C++语言）（全程视频讲解版）》

ISBN：9787302585183

作者：李春葆、匡志强、蒋林

定价：69.8元

内容简介

本书是《数据结构教程（C++语言描述）》（第2版微课视频版）（李春葆等编著，清华大学出版社，以下简称为《教程》）的配套实战题和在线编程题实训指导书，详细给出了《教程》中所有实战题和在线编程题的解题思路和参考源代码，提供了全部题目的讲解视频。书中实战题和在线编程题不仅涵盖数据结构课程的基本知识点，还融合了各个知识点的运用和扩展，学习、理解和借鉴这些内容是掌握和提高编程能力的**捷径。本书自成一体，可以脱离《教程》单独使用，适合高等院校计算机及相关专业的学生使用。

精彩推荐