What is the core pattern used in solving the Couples Holding Hands problem?

The problem is primarily solved through graph traversal, especially using depth-first search (DFS) to model the couples as connected components in the graph.

How do swaps work in the Couples Holding Hands problem?

A swap involves choosing two people who are not sitting next to each other and swapping their positions until all couples are seated together.

Can a greedy approach be applied to the Couples Holding Hands problem?

Yes, a greedy approach can work by making local optimal swaps at each step, such as swapping people until each couple is seated next to each other.

Is Union-Find a good approach for the Couples Holding Hands problem?

Yes, Union-Find is effective for tracking and grouping people who should sit together, efficiently handling swaps needed to group each couple.

What is the time complexity of the Couples Holding Hands problem?

The time complexity depends on the approach: DFS is O(n), and Union-Find has a time complexity of O(α(n)) for each union-find operation.

#765

Hard

auto_awesome图·DFS·traversal

LeetCode 题解工作台

情侣牵手

n 对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手。人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的 ID 。情侣们按顺序编号，第一对是 (0, 1) ，第二对是 (2, 3) ，以此类推，最后一对是 (2n - 2, 2n - 1) 。返回最少交…

贪心深度优先搜索广度优先搜索并查集图

题目描述

n 对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手。

人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n - 2, 2n - 1)。

返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起。每次交换可选择任意两人，让他们站起来交换座位。

示例 1:

输入: row = [0,2,1,3]
输出: 1
解释: 只需要交换第二个人（row[1]）和第三个人（row[2]）的位置即可。

示例 2:

输入: row = [3,2,0,1]
输出: 0
解释: 无需交换座位，所有的情侣都已经可以手牵手了。

提示:

2n == row.length
2 <= n <= 30
n 是偶数
0 <= row[i] < 2n
row 中所有元素均 无重复

lightbulb

解题思路

方法一：并查集

我们可以给每一对情侣编号，编号 $0$ 和 $1$ 的人对应情侣 $0$ ，编号 $2$ 和 $3$ 的人对应情侣 $1$ ...即编号为 $row[i]$ 对应的情侣编号为 $\lfloor \frac{row[i]}{2} \rfloor$ 。

如果有 $k$ 对情侣相互之间坐错了位置，也即是说，有 $k$ 对情侣处于一个置换环中，那么他们之间需要经过 $k-1$ 次交换才能都坐到正确的位置上。

为什么？不妨这样考虑，我们先调整一对情侣的位置，使其坐到正确的位置上，那么问题就从 $k$ 对情侣的问题，转换成了 $k-1$ 对情侣的问题。依此类推，最终 $k=1$ 时，交换次数为 $0$ 。所以，如果 $k$ 对情侣相互之间坐错了位置，那么需要 $k-1$ 次交换。

因此，我们只需要遍历一遍数组，利用并查集找出有多少个置换环，假设有 $x$ 个，每个环的大小（情侣的对数）为 $y_1, y_2, \cdots, y_x$ ，那么需要交换的次数为 $y_1-1 + y_2-1 + \cdots + y_x-1 = y_1 + y_2 + \cdots + y_x - x = n - x$ 。

时间复杂度 $O(n \times \alpha(n))$ ，空间复杂度 $O(n)$ 。其中 $\alpha(n)$ 为阿克曼函数的反函数，可以认为是一个很小的常数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        n = len(row) >> 1
        p = list(range(n))
        for i in range(0, len(row), 2):
            a, b = row[i] >> 1, row[i + 1] >> 1
            p[find(a)] = find(b)
        return n - sum(i == find(i) for i in range(n))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of graph traversal and the ability to apply DFS in a seating arrangement problem.
question_mark
Assess the candidate's ability to use greedy algorithms in a constrained optimization scenario.
question_mark
Evaluate knowledge of union-find and its application to solve seating problems efficiently.

warning

常见陷阱

外企场景

error
Failing to identify the problem as a graph traversal task can lead to inefficient solutions.
error
Not considering all possible swap configurations, leading to suboptimal results.
error
Using the wrong data structures, such as simple arrays instead of graph-related structures, can complicate the solution.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of using swaps, solve the problem using only adjacent seat moves.
arrow_right_alt
Modify the problem to consider a situation where multiple people can swap at once.
arrow_right_alt
Instead of ensuring only couples are next to each other, generalize to a larger group problem, where people need to be grouped with others of specific criteria.

help

常见问题

外企场景

继续练习

#785 判断二分图 #685 冗余连接 II #684 冗余连接