找出列表中的元素对升序排列

如果有输入 a, ..., a, n 为偶数且 a ∈ . 使用曼哈顿距离为距离方程，即 dis(a, a) = | a a |. 输出应为列表中的 n/2 个元素对，以距离升序排列。

如 input [1, 0.4, 3, 1.1], output [(1, 1.1), (0.4, 3)].

input [1, 0.1, 2, 2.4, 3, 4, 1.5], output [(2, 2.4), (1, 1.5), (3, 4)].

我自己想是用笨办法算出所有 C(n,2)的组合计算距离再排列。

def not_in_pair_of_list(i, ls): return not i in [p[0] for p in ls] + [p[1] for p in ls] def calc(ls): ls = sorted(ls) d ={} for idx1, i in enumerate(ls[:-1]): for idx2, j in enumerate(ls[idx1+1:], idx1 + 1): d[(i,j)] = j - i res = [] for pair in sorted(d, key = lambda k: d[k]): i, j = pair if not_in_pair_of_list(i, res) and not_in_pair_of_list(j, res): res.append(pair) return res ls = [1, 0.1, 2, 2.4, 3, 4, 1.5] assert calc(ls) == [(2, 2.4), (1, 1.5), (3, 4)] 

可这只有 O(n)。有没有大神支招，看看有没有更快的。我觉得用 minheap 可以，但提取出新元素对时还要重新计算。