python合并未排序列表 – 算法分析

发布时间：2020-12-20 13:52:56 所属栏目：Python 来源：网络整理

导读：给定两个具有以下结构的数组： array = [(index_1,item_1),(index_2,item_2),...,(index_n,item_n)] 在数组中,项可以是无序的,例如两个Python列表： arr1 = [(1,'A'),(2,'B'),(3,'C')]arr2 = [(3,'c'),'b'),(1,'a')] 我想分析这些数组的合并.我有两种方法可

给定两个具有以下结构的数组：

array = [(index_1,item_1),(index_2,item_2),...,(index_n,item_n)]

在数组中,项可以是无序的,例如两个Python列表：

arr1 = [(1,'A'),(2,'B'),(3,'C')]
arr2 = [(3,'c'),'b'),(1,'a')]

我想分析这些数组的合并.我有两种方法可以考虑进行合并.第一个是对两者的天真迭代
数组：

merged = []
for item in arr:
    for item2 in arr2:
        if item[0] == item2[0]:
            merged.append((item[0],item[1],item2[1]))

# merged
# [(1,'A','a'),'B','C','c')]

这种天真的方法是在大O(n ** 2),

稍微好一点(？)的方法是首先对数组进行排序(使用Python排序为O(n log n))：

arr.sort(key=lambda t: t[0])
arr2.sort(key=lambda t: t[0])

for idx,item in enumerate(arrs):
    merged_s.append(tuple(list(item)+[arr2s[idx][1]]))

所以这种方法总共是O(n log n),这个分析是否正确？
那些列表长度m和n不等的情况怎么样？
有没有一种更有效的方法然后先排序？

解决方法

就你的分析而言,你在两个方面都是正确的.

假设n> m：你的第一个例子是在O(n * m)运行,你的第二个O(nlogn),因为较大的排序支配较小的排序. (注意：假设它运行！当n！= m时,第二种方法很有可能导致错误 – 如果len(arr1)> len(arr2)引发索引错误,或者它会在arr2结束时丢失项目)

我们可以做得更好.
鉴于您的第一个样本不能确保有序输出,我假设这不是一个要求.如果是这样,下面将a)在O(n m)中运行并且b)跳过在两个列表中都找不到密钥的项目.

import itertools
arr1 = [(1,'C'),(4,'D')]
arr2 = [(3,(5,'E')]

output_dict = {}
for key,value in itertools.chain(arr1,arr2): # I like itertools
    output_dict.setdefault(key,[]).append(value)
output = [(key,)+tuple(values) for key,values in output_dict.items() if len(values)==2]

输出将是：

[(1,'c')]

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!