时间戳

首页 > 解决方案 > 如何在线性时间内根据键重新组合列表列表？

python - 如何在线性时间内根据键重新组合列表列表？

问题描述

嗨，我是 Python 新手，我有一个列表列表

arr=[['act', 'abd'], ['cat', 'act'], ['tac', 'act'], ['bad', 'act'], ['fad', 'adf ']]

我想使用 arr[index][1]（在这种情况下是它的 'act'、'abd' 和 'adf'）作为在 O(N) 时间内重新组合我的列表列表的关键，其中 N是输入列表：

arr=[['act','act','cat','tac'],['abd','bad'],['adf','fad']]

这是我尝试过的，但输出没有意义：

def groupList(a_list):
index=0
searchList=[]
while index<len(tempList)-1:
    key=tempList[index][1]
    newList=[]
    newList.append(key)
    newList.append(tempList[index][0])
    if tempList[index+1][1]==key:
        newList.append(tempList[index+1][0])
    else:
        searchList.append(newList)
    index+=1
print(searchList)

输出是：

[['abd', 'act'], ['act', 'bad']]

任何帮助将不胜感激谢谢

标签： pythonlistloopsanagram

解决方案

比你的代码简单，我有这个：

arr= [['act', 'act'], ['cat', 'act'], ['tac', 'act'], ['bad', 'abd'],['fad', 'adf']] 

new_arr = []
keys = []

for elt in arr:
    if elt[1] not in keys:
        # apparently you want the key first
        new_arr.append([elt[1], elt[0]])
        keys.append(elt[1])
    else:
        id = keys.index(elt[1])
        new_arr[id].append(elt[0])

它只是查看是否已经遇到了键，如果是，它会寻找放置新元素的位置。

输出：

new_arr
Out: [['act', 'act', 'cat', 'tac'], ['abd', 'bad'], ['adf', 'fad']]

但是，这不是 O(n)，因为.index()方法和in. 是 O(n²)。

注意：我怀疑这可以在 O(n) 中完成，因为您需要一个 for 循环来循环输入，并且对于每个元素，您需要查看它是否需要放置在新的子列表中或现有的子列表中。

推荐阅读