算法:删除有序数组中的重复项---双指针[3]

这篇具有很好参考价值的文章主要介绍了算法:删除有序数组中的重复项---双指针[3]。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

文章来源:
https://blog.csdn.net/weixin_45630258/article/details/132701024
欢迎各位大佬指点、三连
算法:删除有序数组中的重复项---双指针[3],算法,算法,java,eclipse,intellij-idea,windows,visual studio,数据结构


1、题目:

对给定的有序数组 nums 删除重复元素,在删除重复元素之后,每个元素只出现一次,并返回新的长度,上述操作必须通过原地修改数组的方法,使用 O(1) 的空间复杂度完成。


2、分析特点:

  • 题目要求:原地修改、 有序数组
  • 原地+删除 ==> 结果数组一定比原数组的长度更短 ,并且,我们可以 把结果数组直接写在原数组上
  • 有序数组 ==> 当前元素和前一个元素是相等的时候,则不需要收集, 我们需要收集的元素,是那些不会等于前一个元素的,充分利用有序的特点 ,继续往前遍历,只要不等于前一个元素,就可以收集起来,等于了就放弃,比如 2 3 3,第一个 3 作为当前元素的时候,和前一个元素不相等,可以收集起来,到了第二个 3 和前一个元素相等了,放弃收集。

3、特点:

有序数组,剔除掉相等的,拿当前位置的元素去和前一个元素比较 ,即if (nums[fast] != nums[fast - 1]); 并且 0 位置的元素早就进入结果集,需要看后面的元素是否进结果,则定义的两个指针开始判断收集的起点下标从1开始。

定义两个指针 fast 和 slow 分别为快指针和慢指针,

快指针表示遍历原数组到达的下标位置,慢指针表示结果数组的下标位置,即下一个不同元素要填入的下标位置,初始时两个指针都指向下标 1。

快指针的范围是从 1 到 最后一个元素位置;

慢指针是从 1 开始不断根据快指针满足了条件就加入收集结果(前提,0位置的元素早就进入了结果,需要看后面的元素是否进结果);


4、代码:


5、复杂度分析:

  • 时间复杂度:O(n),其中 n 是数组的长度。快指针和慢指针最多各移动 n 次。
  • 空间复杂度:O(1)。只需要使用常数的额外空间。

6、总结:

有序数组,剔除掉相等的,拿当前位置的元素去和前一个元素比较,即if (nums[fast] != nums[fast - 1]); 并且 0 位置的元素早就进入结果集,需要看后面的元素是否进结果,则定义的两个指针开始判断收集的起点下标从1开始。




如果本文对你有帮助的话记得给一乐点个赞哦,感谢!文章来源地址https://www.toymoban.com/news/detail-705222.html

到了这里,关于算法:删除有序数组中的重复项---双指针[3]的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【Leetcode】26.删除有序数组中的重复项

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

    2024年02月12日
    浏览(48)
  • 115.删除有序数组中的重复项 removeDuplicatesFromSortedArray

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

    2024年02月06日
    浏览(41)
  • 80. 删除有序数组中的重复项 II

    题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台  解题思路:因为数组有序,相等的元素一定相邻,所以可以使用一个变量num统计相等元素的个数,如果当前元素和前一个元素相等,令num++。另外使用一个变量len记录删除后数组的新长度,如果当前正在遍历的元

    2024年02月13日
    浏览(45)
  • LeetCode26.删除有序数组中的重复项

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

    2023年04月22日
    浏览(48)
  • 力扣0080——删除有序数组中的重复项II

    难度: 中等 给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使得出现次数超过两次的元素 只出现两次 ,返回删除后数组的新长度。 不要使用额外的数组空间,你必须在 原地 修改输入数组并在使用 O(1) 额外空间的条件下完成。 说明 : 为什么返回数值是整数,但

    2024年02月21日
    浏览(36)
  • 面试经典150题——删除有序数组中的重复项

    题目来源 力扣每日一题;题序:26 我的题解 方法一 双指针 使用两个指针分别指向相同元素的左右边界,再利用一个count记录最终需要的数组长度。 时间复杂度 :O(n) 空间复杂度 :O(1) 有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持

    2024年04月14日
    浏览(54)
  • (78)删除有序数组中的重复项(79)排序矩阵查找

    水晶帘动微风起,满架蔷薇一院香。 —高骈- 题目链接:删除有序数组中的重复项 给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个

    2024年04月17日
    浏览(36)
  • 图灵日记之Leetcode删除有序数组中的重复项&&合并两个有序数组&&移除链表元素

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

    2024年02月04日
    浏览(58)
  • 【每日一题】2.LeetCode——删除有序数组中的重复项

    📚博客主页:爱敲代码的小杨. ✨专栏:《Java SE语法》 ❤️感谢大家点赞👍🏻收藏⭐评论✍🏻,您的三连就是我持续更新的动力❤️ 🙏小杨水平有限,欢迎各位大佬指点,相互学习进步! 给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元

    2024年02月19日
    浏览(50)
  • 【数据结构OJ题】删除有序数组中的重复项

    原题链接:https://leetcode.cn/problems/remove-duplicates-from-sorted-array/ 目录 1. 题目描述 2. 思路分析 3. 代码实现 用 双指针算法, 定义两个变量src和dst,一开始让src和dst指向num[ ]数组的第一个元素,再使用if语句判断。 如果nums[src]==nums[dst],就让src指向下一位,即src++。如果nums[src]!=

    2024年02月14日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包