情侣牵手

发表于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

LeetCode每日一题，765. Couples Holding Hands

先看题目描述

[yyyqpV.png](https://imgchr.com/i/yyy5wj)

大意就是 N 对情侣坐在连续的 2N 个座位上，想要每对情侣并肩坐在一起，计算最少需要的交换次数，情侣和座位均按顺序编号

算法和思路

并查集

这题不会，看题解才懂得

我们将 N 对情侣看做图中的 N 个节点；对于每对相邻的位置，如果是第 i 对与第 j 对坐在了一起，则在 i 号节点与 j 号节点之间连接一条边，代表需要交换这两对情侣的位置

如果图中形成一个大小为 k 的环，则我们沿着环的方向，进行了 k - 1 次交换后，这 k 对情侣就能够彼此牵手了

故我们只需要利用并查集求出图中的每个连通分量；对于每个连通分量而言，其大小减 1 就是需要交换的次数

最后要返回的答案就是情侣对数 - 连通分量个数，即设图中有 N 个节点， n 个连通分量，最后返回 N - n 即可

算法源码

并查集

并查集中使用了路径压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    private  int count;

    public int minSwapsCouples(int[] row) {
        int N = row.length / 2;
        this.count = N;
        int[] parent = new int[N];
        for (int i = 0; i < N; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < N; i++) {
            union(row[2 * i] / 2, row[2 * i + 1] / 2, parent);
        }
        return N - this.count;
    }

    private int find(int x, int[] parent) {
        if (x != parent[x]) {
            parent[x] = find(parent[x], parent);
        }
        return parent[x];
    }

    private void union(int a, int b, int[] parent) {
        int x = find(a, parent);
        int y = find(b, parent);
        if (x == y) {
            return;
        }
        parent[y] = x;
        this.count--;
    }
}