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

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

1

【实战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++。

2

视频讲解

3

参考书籍

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

ISBN：9787302585183

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

定价：69.8元

内容简介

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

3

精彩推荐

• 微信小程序游戏开发│猜数字小游戏（附源码+视频）

• Flink编程基础│Scala编程初级实践

• Flink编程基础│FlinkCEP编程实践

• Flink编程基础│DataStream API编程实践

• Flink编程基础│DataSet API编程实践

• 数据分析实战│客户价值分析

• 数据分析实战│价格预测挑战

• 数据分析实战│时间序列预测

• 数据分析实战│KaggleTitanic生存预测