python - 将值添加到同一字典中的键

Question

这将是我的输入

{1: [2, 3], 2: [1, 7], 3: [1], 7: [1]}

输出:

{1: [2, 3, 1, 7, 1], 2: [1, 7, 2, 3, 1, 7, 1, 1], 3: [1, 2, 3, 1, 7, 1],
 7: [1, 2, 3, 1, 7, 1]}

这里发生的是对于每个 key , value values在给定 key 的值列表内将充当键本身以及与新的 key 相对应的值应附在原文之后。

现在让我说得非常清楚。以此为例。

simple_dict={1:[2,3],2:[7],3:[1],7:[1]}这里将使用一把 key ，比如 1现在它的所有值 2 , 3本身将充当 key 。所以simple_dict[2] , simple_dict[3]将被添加到原始 key 中，以便我得到 1:[2,3,7,1]这样的。对于所有键都应该以同样的方式完成此操作。

目前我尝试过这个!

my_dict = {1:[2,3],2:[7],3:[1],7:[1]}
print(my_dict)
for k,v in my_dict.items():
    for i in v:
        my_dict[k]=my_dict[k]+my_dict[i]
print(my_dict)

输出:

{1: [2, 3], 2: [7], 3: [1], 7: [1]}
{1: [2, 3, 7, 1], 2: [7, 1], 3: [1, 2, 3, 7, 1], 7: [1, 2, 3, 7, 1]}

这效果很好。但时间复杂度好像是O(n^2)

(我对时间复杂度的理解是否正确，即这将是 O(n^2) 复杂度？或者会比这小得多？)

我想做的事情有更简单的方法吗？非常欢迎任何建议、想法。

Answer 1

This works well and good. But the time complexity seems to be O(n²)

实际上更糟:时间复杂度为O(n³)，因为将两个列表添加在一起将在内完成>O(n) 时间，并且对每个键都执行 O(n) 时间(这又是 O(n))。

尽管如此，这里还有另一个问题更新顺序很重要:因为您写入my_dict[k]，这意味着如果您处理新项目，字典将已更新。这可能不是预期的行为。

这里你能做的最好的事情就是构建一个O(n²)算法(假设你不创建函数式编程列表)，因为输出可以生成一个对象大小O(n²)，对此你无能为力，它是“理论下限”(除非，如前所述，你工作带有指向不可变数据结构的指针，但这些不再是列表)。

您可以制作一个优雅的列表理解，它可以在 O(n²) 中工作:

{k:vs+[vi for v in vs for vi in my_dict[v]] for k,vs in my_dict.items()}

这将构造:

>>> { k : vs + [vi for v in vs for vi in my_dict[v]] for k,vs in my_dict.items()}
{1: [2, 3, 1, 7, 1], 2: [1, 7, 2, 3, 1], 3: [1, 2, 3], 7: [1, 2, 3]}

它假设字典列表中的所有索引都是有效索引:这些索引都在字典中。如果情况并非总是如此，您可以使用以下表达式使程序更加安全:

{k:vs+[vi for v in vs for vi in my_dict.get(v,())] for k,vs in my_dict.items()}

现在我们添加了 () 作为后备值，这样当找不到键时，它不会向列表中添加任何内容。