你的问题主要在于读书不多而想的太多。——杨绛
这句话说的真是太对了,我一定多读书!!!
题目:给定一个无序链表,例如:head->1->2>1-->3->3->5->7->6>7->8,删除其中的重复项,将其变成head->1->2->5->7->6->8。
今天的题目与昨天的题目是相同的,昨天我们用的顺序删除法,成功的完成了这个任务。但是其采用双重循环来遍历链表,时间复杂度为O(N^2)。通常情况下,为了降低时间复杂度,往往再条件允许的情况下,通过使用辅助空间来实现。具体如下:
题目要求去除重复项,我们很容易想到Python自己的一种数据类型——集合set。集合具有无序性、唯一性、确定性。无序性:集合中的元素的地位相同,没有顺序。唯一性:也叫互异性,集合元素两两各不相同,每个元素只能出现一次。确定性:给定一个集合,任给一个元素,该元素或者属于或者不属于该集合,二者必居其一,不允许有模棱两可的情况出现。
我们利用集合的唯一性就可以解决——“当前节点是否重复出现过”这一问题了。我们先建立一个HashSet集合,HashSet用来存储已经遍历过的节点的内容。先将其初始化为空。然后从头开始遍历链表,然后判断当前节点的内容是否在HashSet中。如果在,则把当前节点删除;如果不在,保留当前节点,并将当前节点的内容添加到HashSet中,遍历下一个节点,直到链表为空。
这种方法的时间复杂度为O(n),因为只需要遍历一次链表。下面用代码实现:
def RemoveDup(head):
"""
空间换时间
无头节点
"""
#先判断链表是否为空或者
if head.next is None:
return head
Hashset=set()#保存已经遍历过的内容
Hashset.clear()#初始化集合
pre=head#指向当前节点的前驱节点,用于删除当前节点
cur=head.next#用于遍历链表,指向当前节点
#遍历链表
while cur is not None:
#如果当前节点的值不在HashSet中,则将其存到HashSet中
if cur.data not in Hashset:
Hashset.add(cur.data)
#遍历下一个节点
cur=cur.next
pre=pre.next
else:
#如果当前节点的值在HashSet中,则删除节点
pre.next=cur.next
cur=cur.next
#返回处理完成的链表
return head
至于如何删除当前节点,这个问题我在昨天的文章里写的很清楚了这里就不在赘述——python算法-005从无序链表中移除重复项(顺序删除法)。
与之前一样先构造一个无序链表(昨天也讲了,可以看看前面的链接),用于检验我们的算法:
#先引入random库
import random
#依然是先定义节点类
class LNode(object):
def __init__(self, arg):
self.data = arg
self.next = None
#这里!前几篇的create我写错了,少了个e,
#这里改用construct 构造的意思
def construstLink(x):
i = 1
head = LNode(None)
tmp = None
cur = head
while i <= x:
#这里与之前不同,先生成一个随机数,作为节点值
n = random.randint(0, 9)
tmp = LNode(n)
cur.next = tmp
cur = tmp
i += 1
return head
主程序:
if __name__ == '__main__':
#构造链表
head=construstLink(10)
#打印处理之前的链表
print("BeforeReverse:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
#调用算法,处理链表
head = RemoveDup(head)
# 打印处理之后的链表
print("\nAfterReverse:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
下面的是运行结果:
你也可以多试几次,我这算法是对的。
这是全部的代码:
import random
class LNode(object):
"""docstring for LNode"""
def __init__(self, arg):
self.data = arg
self.next = None
#这里!前几篇的create我写错了,少了个e,
#这里改用construct 构造的意思
def construstLink(x):
i = 1
head = LNode(None)
tmp = None
cur = head
while i <= x:
#这里与之前不同,先生成一个随机数,作为节点值
n = random.randint(0, 9)
tmp = LNode(n)
cur.next = tmp
cur = tmp
i += 1
return head
"""
题目描述:
将Head->1->1->3->3->5->7->7->8变
为head->1->2->5->7->8
方法:空间换时间,利用集合的无序性、唯一性
"""
def RemoveDup(head):
"""
空间换时间
无头节点
"""
#先判断链表是否为空或者
if head.next is None:
return head
Hashset=set()#保存已经遍历过的内容
Hashset.clear()#初始化集合
pre=head#指向当前节点的前驱节点,用于删除当前节点
cur=head.next#用于遍历链表,指向当前节点
#遍历链表
while cur is not None:
#如果当前节点的值不在HashSet中,则将其存到HashSet中
if cur.data not in Hashset:
Hashset.add(cur.data)
#遍历下一个节点
cur=cur.next
pre=pre.next
else:
#如果当前节点的值在HashSet中,则删除节点
pre.next=cur.next
cur=cur.next
#返回处理完成的链表
return head
if __name__ == '__main__':
#构造链表
head=construstLink(10)
#打印处理之前的链表
print("BeforeRemoveDup:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
#调用算法,处理链表
head = RemoveDup(head)
# 打印处理之后的链表
print("\nAfterRemoveDup:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
今天的算法就这样,明天讲一讲如何用递归来实现这种操作,大家可以先试一试。我目前也是在学习阶段,还有存在很多问题,望各位不吝赐教。我写这类文章,一是为了能够更好的理解我学的东西,毕竟自己能讲出来,也是很不错了;二呢,是为了与大家分享我的学习成果,一起学习一起进步,一起走向人生巅峰(哈哈哈,当然光学这个,那是连工作都不一定能找到);还有一点就是:有一件能够坚持的事情也是很幸福的!
当然大家有什么需要都可以来找我,简书号、微信公众号:Dkider 私信、简信,都可以找到我。
更多的问题以及文章源码见github。
要人知道自己有个秘密,而不让人知道是个什么秘密,等他们问,要他们猜,这是人性的虚荣。——钱钟书《围城》