您的位置首页  桂林文化  影视

数据结构C++|实例:LeetCode26—删除排序数组中的重复项(附视频)

数据结构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生存预测

免责声明:本站所有信息均搜集自互联网,并不代表本站观点,本站不对其真实合法性负责。如有信息侵犯了您的权益,请告知,本站将立刻处理。联系QQ:1640731186
TAGS标签更多>>