python - 通过一个元组的第一个元素和另一个元组的第二个元素相等来排序元组列表

Question

我有一个表示点 (x, y) 的元组列表，我想对它们进行排序，如果点 p_i 的 x_i等于另一点p_j的y_j。这些点使得 x 和 y 从不在点之间重复，例如给定点 (1,2)，不允许任何 x 和 y 的点 (1,y) 或 (x, 2)。例如:

points = [(1, 5), (3, 4), (5, 3), (4, 1), (7,2), (2, 6)]  # valid points

应按 [(1, 5), (5, 3), (3, 4), (4, 1), (7, 2), (2, 6)]

这是我为此编写的代码:

N = len(points)
for i in range(N):
    for j in range(i + 1, N):
        if points[i][1] == points[j][0]:
            points.insert(i + 1, points.pop(j))
            break

不幸的是，它的复杂度是 O(N^2) 并且对于大量的点来说它很慢。有没有办法更快地做到这一点？

Answer 1

将您的无序列表视为对有向图的描述，其中每个节点都在某个唯一链中，您可以进行以下抽象。

points = [(1, 5), (3, 4), (5, 3), (4, 1), (7,2), (2, 6)]

# Create the graph and initialize the list of chains
graph, chains, seen = dict(points), [], set()

# Find the chains in the graph
for node, target in graph.items():
    while node not in seen:
        seen.add(node)
        chains.append((node, target))
        node = target
        try:
            target = graph[target]
        except KeyError:
            break

# chains : [(1, 5), (5, 3), (3, 4), (4, 1), (7, 2), (2, 6)]

这为我们提供了一个在 O(n) 中运行的算法。