python - 删除元组列表中除整数之间间隙最小的所有元组

Question

我需要从元组列表中删除所有元组，除了那些彼此最接近的整数对。

例如，我有一个列表:

[(7, 36), (8, 36), (9, 36), (12, 36), (13, 37), (15, 37), (23, 37), ( 65, 78)]


我希望它看起来像这样:

[(12, 36), (23, 37), (65, 78)]

换句话说，第一个值必须是最大的，或者元组中两个数字之间的差距必须是最小的。问题是，我事先并不知道第一个数字，也不知道第二个数字。我也不知道附加了多少元组。

使用python3.5

UPD:非常感谢您的回答!编辑后，所有这些都可以正常工作。

Answer 1

我会用 OrdereDict 来解决这个问题:

在 Python 2 中，我会这样写:

>>> from collections import OrderedDict
>>> l = [(7, 36), (8, 36), (9, 36), (12, 36), (13, 37), (15, 37), (23, 37), (65, 78)]
>>> 
>>> seen = OrderedDict()
>>> for first, second in l:
...     if first > seen.get(second, None):
...         seen[second] = first
... 
>>> [(x, y) for y, x in seen.items()]
[(12, 36), (23, 37), (65, 78)]

请注意，所有内容都将大于 seen.get 的回退值 None。

Python 3+ 解决方案，您无法将整数与 None 进行比较:

>>> seen = OrderedDict()
>>> for first, second in l:
...     if second not in seen or first > seen[second]:
...         seen[second] = first
... 
>>> [(x, y) for y, x in seen.items()]
[(12, 36), (23, 37), (65, 78)]

两种解决方案都不限于正整数元组。此操作的运行时间为 O(n)，因为不涉及 O(n log(n)) 排序。