Python中比较两个列表并执行指定操作的实现方案

需求说明 #

给定两个列表I和i，需要对i中的每个元素执行以下操作：

1. 找出I中所有小于该元素的值
2. 将这些值的数量加到原元素上，生成新列表New i
3. 同时记录每个元素对应的I中小于它的所有值，形成列表Values

示例输入 #

I = [8, 11, 19, 37, 40, 42]
i = [15, 17, 27, 28, 31, 41]

预期输出 #

New i = [17, 19, 30, 31, 34, 46]
Values = [[8,11],[8,11],[8,11,19],[8,11,19],[8,11,19],[8,11,19,37,40]]

解决方案 #

由于示例中的I是有序列表，我们可以利用Python的bisect模块高效完成查找操作，避免逐个遍历的低效问题。如果I是无序的，只需先对其副本排序即可（不影响原列表）。

代码实现 #

import bisect

# 输入列表
I = [8, 11, 19, 37, 40, 42]
i_list = [15, 17, 27, 28, 31, 41]

new_i = []
values = []

for num in i_list:
    # 找到第一个大于等于当前元素的索引，即小于当前元素的数量
    count = bisect.bisect_left(I, num)
    # 提取所有小于当前元素的值
    less_values = I[:count]
    # 计算新元素值
    new_num = num + count
    # 添加到结果列表
    new_i.append(new_num)
    values.append(less_values)

# 输出结果
print(f"New i={new_i}")
print(f"Values={values}")

代码说明 #

• bisect.bisect_left(I, num)：返回num在有序列表I中应插入的位置，该位置恰好等于I中小于num的元素个数
• I[:count]：通过切片直接获取所有小于num的元素，无需额外遍历
• 时间复杂度：每个元素的查找操作是O(log n)，整体复杂度为O(m log n)（m是i的长度，n是I的长度），比暴力遍历的O(m*n)高效得多

内容的提问来源于stack exchange，提问作者user20032724