情侣牵手

Couples Holding Hands

问题：情侣牵手

考察：贪心、深度优先搜索、广度优先搜索

来源：DSA Prep / Citadel

链接：https://leetcode.com/problems/couples-holding-hands

Problem: Couples Holding Hands

Patterns: Greedy, Depth-First Search, Breadth-First Search

Recency: 2yr

Link: https://leetcode.com/problems/couples-holding-hands

Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/

解析

思路：把每对情侣看作一个组，当前座位相邻两人若不是一对，就把其中一人的伴侣交换到旁边。也可建图/并查集：每个连通块大小为 m，需要 m-1 次交换。

复杂度：贪心配合位置表 O(n)，空间 O(n)。