python之如果嵌套列表中不存在元素，如何有效地检查和添加

我有一个巨大的嵌套列表，它的元素是具有以下形式的字符串:

[[0,'+','the','+','quick','+','brown','+','fox','+','jumps','over','+','the','+','lazy','+','dog','+',908] 
..., 
['Now','+','is','+', 'the','+', 'time','+', 'for','+', 'all','+', 67,'+', 'men']] 

但是，我发现有些元素没有 + 分隔符。例如，在子列表一中:

[0,'+','the','+','quick','+','brown','+','fox','+','jumps','over','+','the','+','lazy','+','dog','+',908] 

在 'jumps','over' 之间缺少 +。对于具有长子列表的大型嵌套列表，在没有分隔符的元素之间添加 + 分隔符的最有效方法是什么？

预期的输出应该是这样的:

[[0,'+','the','+','quick','+','brown','+','fox','+','jumps','+','over','+','the','+','lazy','+','dog','+',908] 
    ..., 
    ['Now','+','is','+', 'the','+', 'time','+', 'for','+', 'all','+', 67,'+', 'men']] 

请您参考如下方法:

有点贪心:

cleansed_lists = [[word for word in sentence if word != '+'] for sentence in nested_list] 
result = [] 
for sentence in cleansed_lists: 
    new_list = ['+'] * (2 * len(sentence) - 1) 
    new_list[::2] = sentence 
    result.append(new_list) 

时间复杂度:

假设 N 是外部列表的长度，n 是每个内部列表(您的句子)的平均长度。

第 1 行:我们使用 O(1) 操作(即 if word != '+ ').因此，第 1 行的时间复杂度为 O(n*N)。

第 3-6 行:我们遍历外部列表一次(第 3 行)，等效 列表的大小是内部列表的两倍(第 4 行) ，以及列表中的每个其他元素，其大小是我们内部列表的两倍(第 5 行)。这会产生 O(N*(2n + n)) 的时间复杂度，这可以简化为 O(n*N)。

= O(n*N) + O(N*(2n+n)) 
= O(n*N) + O(N*3n) 
= O(n*N) + O(N*n) 
= O(n*N) 

因此，最终的复杂度是O(n*N)。