Python高效算法：求解列表元素第三大差值问题

问题描述 #

假设有n个人（n>4），编号0至n-1，每人对应列表p中的一个性格值（可负）。两人间的愉悦值定义为|p[i] - p[j]|（i≠j）。需实现函数third_enjoyment(p: list[int]) -> list[int]，返回原列表中每个元素对应的第三大愉悦值。例如输入[2,3,4,6]时，输出为[1,1,1,2]。

当前暴力解法（如下）时间复杂度为O(n²)，在数据量较大时会超时，需要更高效的实现：

def third_enjoyment(p: list[int]) -> list[int]:
    n: int = len(p)
    e: list[int] = []

    for i in range(n):
        enjoyment = [abs(p[i] - p[j]) for j in range(n) if j != i]
        enjoyment.sort()
        third_enjoyment = enjoyment[-3]
        e.append(third_enjoyment)

    return e

优化思路 #

暴力解法的核心问题是对每个元素都要遍历全部其他元素并排序，导致O(n²)的时间开销。实际上，绝对值的大小和元素在排序后的位置直接相关：排序后的数组中，某个元素的最大几个愉悦值必然来自它左右相邻的几个元素，无需遍历整个数组。

具体优化步骤：

1. 对原数组排序，同时保留每个元素的原索引（最终结果需要对应原数组的顺序）。
2. 对排序后的每个元素，只需要考虑它左右各最多3个相邻元素（第三大的愉悦值一定来自最近的几个邻居），计算这些邻居与当前元素的愉悦值。
3. 收集候选愉悦值后排序，取第三大的值，再通过原索引映射回结果数组的对应位置。

该方案的时间复杂度主要来自排序的O(n log n)，远低于暴力解法的O(n²)，适合处理大规模数据。

高效实现代码 #

def third_enjoyment(p: list[int]) -> list[int]:
    n = len(p)
    # 排序时保留每个元素的原索引
    sorted_pairs = sorted((val, idx) for idx, val in enumerate(p))
    sorted_vals = [val for val, idx in sorted_pairs]
    result = [0] * n

    for i in range(n):
        current_val = sorted_vals[i]
        candidates = []
        # 取左侧最多3个元素计算愉悦值
        left_start = max(0, i - 3)
        for j in range(left_start, i):
            candidates.append(abs(current_val - sorted_vals[j]))
        # 取右侧最多3个元素计算愉悦值
        right_end = min(n, i + 4)
        for j in range(i + 1, right_end):
            candidates.append(abs(current_val - sorted_vals[j]))
        # 排序后取第三大的愉悦值
        candidates.sort()
        third_max = candidates[-3]
        # 将结果映射回原数组的位置
        result[sorted_pairs[i][1]] = third_max
    
    return result

验证示例 #

输入[2,3,4,6]时：

• 排序后的数组为[(2,0), (3,1), (4,2), (6,3)]
• 原索引0的元素2，候选愉悦值为1、2、4，第三大是1
• 原索引1的元素3，候选愉悦值为1、1、3，第三大是1
• 原索引2的元素4，候选愉悦值为2、1、2，第三大是1
• 原索引3的元素6，候选愉悦值为4、3、2，第三大是2
  最终输出[1,1,1,2]，符合预期。

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