前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >删除排序数组中的重复项

删除排序数组中的重复项

作者头像
木瓜煲鸡脚
发布2020-09-23 12:44:10
5K0
发布2020-09-23 12:44:10
举报
文章被收录于专栏:Jasper小笔记Jasper小笔记

给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:

代码语言:javascript
复制
给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

代码语言:javascript
复制
给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

问题信息
  1. 输入:已排好序的数组
  2. 输出:去重后新数组的长度
  3. 额外条件:不创建额外空间直接修改原数组去重,不考虑新数组长度之后的元素
思考

很显然需要遍历扫描重复项,在元素不同的时候设置值。那么需要两个指针比较,一个指针i的功能是用来存去重的值,因此第二个指针j扫面全部与i判断是否重复若不重复则i指针要移动并存下该值。

代码语言:javascript
复制
/*
给定 nums = [0,0,1,1,1,2,2,3,3,4],
第一位是直接不变,从第二位才开始需要判断
*/
nums[1] == nums[0] 相等
nums[2] == nums[0] 不相等 存下第二位 num[1] = nums[2]
nums[3] == nums[1] 相等
nums[4] == nums[1] 相等
nums[5] == nums[1] 不相等 存下第三位 nums[2] = nums[5]
nums[6] == nums[2] 相等
......

总结代码

代码语言:javascript
复制
int i = 0;
for(int j = 1; j < nums.length; j++){
    if(nums[j] != nums[i]){
        i++;
        nums[i] = nums[j];
    }
}
return i+1

数组长度是固定的所以设置不重复的值后后面的以前的值还是存在的,按照题意不去创建新数组只要得到新数组的大小即可,也就是nums[0]到nums[i]就是可以取走做新数组,按照例子去重后原数组nums = [0,1,2,3,4,2,2,3,3,4]。原数组的前i+1位即是新数组元素,长度即i+1

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-09-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 IT那个小笔记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 问题信息
  • 思考
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档