合并排序 2 列表查找共同元素
Merge Sort 2 Lists Finding Common Elements
对于一项作业,我们被要求编写一个函数,该函数将 2 个列表作为输入,然后 returns 一个包含 'list 1' 和 'list 2' 中的所有名称的列表.
已要求使用基于合并排序的算法来完成。到目前为止,我得到的是 returns 正确的列表,但是我进行了太多的比较以获取此列表。 VoterList 是指定的 class 给我们的,这样我们就不会使用普通的 python 列表。只有 VoterName 对象(两个输入列表的组成部分)能够附加到 VoterList。传入的列表均按字典顺序排列。
欢迎就如何减少我的比较提出任何建议。谢谢。
from classes import VoterList
def fraud_detect_merge(first_booth_voters, second_booth_voters):
fraud = VoterList()
length_first = len(first_booth_voters)
length_second = len(second_booth_voters)
first_booth_position = 0
second_booth_position = 0
comparisons = 0
while first_booth_position < length_first:
if second_booth_position == length_second:
first_booth_position += 1
second_booth_position = 0
else:
name_comparison = first_booth_voters[first_booth_position]
comparisons += 1
if second_booth_voters[second_booth_position] == name_comparison:
fraud.append(second_booth_voters[second_booth_position])
first_booth_position += 1
second_booth_position = 0
else:
second_booth_position += 1
return fraud, comparisons
不清楚你输入的是什么,是否已经排序?正在为您提供清单。查看可以对列表执行哪些操作,您会发现 pop()
操作。这将从列表中删除一项并为您提供它的值。由于列表都是按顺序排列的,因此可以使用以下方法:
def fraud_detect_merge(first_booth_voters, second_booth_voters):
fraud = VoterList()
comparisons = 0
first_booth_voters.sort() # if not already sorted
second_booth_voters.sort() # if not already sorted
first = first_booth_voters[0]
second = second_booth_voters[0]
while first_booth_voters and second_booth_voters:
comparisons += 1
if first == second:
fraud.append(first)
first = first_booth_voters.pop(0)
second = second_booth_voters.pop(0)
elif first < second:
first = first_booth_voters.pop(0)
else:
second = second_booth_voters.pop(0)
return fraud, comparisons
作业正好要求你找到一个解决方案,并且有合并排序的重要提示,所以我不会为你泄露答案:)但是也许我可以指出你的代码中发生了什么:在最坏的情况下,你的 while 循环基本上完成了两个长度为 length_first
和 length_second
的嵌套循环:
for name_comparison in first_booth_voters:
for second_name in second_booth_voters:
comparisons += 1
if second_name == name_comparison:
fraud.append(second_name)
break
这导致在最坏的情况下进行 length_first x length_second
比较。鉴于输入列表已排序,这当然不是最佳选择。您需要利用排序。如果输入列表未排序,您应该考虑将 harder-to-read/debug/understand while 循环替换为更具可读性的嵌套 for 循环。
对于一项作业,我们被要求编写一个函数,该函数将 2 个列表作为输入,然后 returns 一个包含 'list 1' 和 'list 2' 中的所有名称的列表.
已要求使用基于合并排序的算法来完成。到目前为止,我得到的是 returns 正确的列表,但是我进行了太多的比较以获取此列表。 VoterList 是指定的 class 给我们的,这样我们就不会使用普通的 python 列表。只有 VoterName 对象(两个输入列表的组成部分)能够附加到 VoterList。传入的列表均按字典顺序排列。
欢迎就如何减少我的比较提出任何建议。谢谢。
from classes import VoterList
def fraud_detect_merge(first_booth_voters, second_booth_voters):
fraud = VoterList()
length_first = len(first_booth_voters)
length_second = len(second_booth_voters)
first_booth_position = 0
second_booth_position = 0
comparisons = 0
while first_booth_position < length_first:
if second_booth_position == length_second:
first_booth_position += 1
second_booth_position = 0
else:
name_comparison = first_booth_voters[first_booth_position]
comparisons += 1
if second_booth_voters[second_booth_position] == name_comparison:
fraud.append(second_booth_voters[second_booth_position])
first_booth_position += 1
second_booth_position = 0
else:
second_booth_position += 1
return fraud, comparisons
不清楚你输入的是什么,是否已经排序?正在为您提供清单。查看可以对列表执行哪些操作,您会发现 pop()
操作。这将从列表中删除一项并为您提供它的值。由于列表都是按顺序排列的,因此可以使用以下方法:
def fraud_detect_merge(first_booth_voters, second_booth_voters):
fraud = VoterList()
comparisons = 0
first_booth_voters.sort() # if not already sorted
second_booth_voters.sort() # if not already sorted
first = first_booth_voters[0]
second = second_booth_voters[0]
while first_booth_voters and second_booth_voters:
comparisons += 1
if first == second:
fraud.append(first)
first = first_booth_voters.pop(0)
second = second_booth_voters.pop(0)
elif first < second:
first = first_booth_voters.pop(0)
else:
second = second_booth_voters.pop(0)
return fraud, comparisons
作业正好要求你找到一个解决方案,并且有合并排序的重要提示,所以我不会为你泄露答案:)但是也许我可以指出你的代码中发生了什么:在最坏的情况下,你的 while 循环基本上完成了两个长度为 length_first
和 length_second
的嵌套循环:
for name_comparison in first_booth_voters:
for second_name in second_booth_voters:
comparisons += 1
if second_name == name_comparison:
fraud.append(second_name)
break
这导致在最坏的情况下进行 length_first x length_second
比较。鉴于输入列表已排序,这当然不是最佳选择。您需要利用排序。如果输入列表未排序,您应该考虑将 harder-to-read/debug/understand while 循环替换为更具可读性的嵌套 for 循环。