首页 > 代码库 > 链表操作 -- 未排序链表的处理问题
链表操作 -- 未排序链表的处理问题
问题:
删除未排序链表中的重复元素。
解答:
1)最朴素的方法就是将链表排序,然后遍历并删除其中的重复元素。这种方法的时间复杂度依赖于排序的过程。
在此,我们要思考一下,找到并且删除链表中的重复元素真的需要排序过程吗?
2)如何才能在不排序的情况下找到重复元素?
最朴素的方法就是处理每个节点的时候,遍历剩余的节点,查看其中是否有重复的元素。这种方法的时间复杂度较高,O(n2)。
有没有更好的算法或是数据结构来帮助我们降低这个时间复杂度?这种查找某个元素的存在性问题,可以借助于hash表来快速的实现。由此,算法的时间复杂度降低为了O(n)。
链表操作 -- 未排序链表的处理问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。