题目链接
N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。
人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)。
这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。
示例 1:
1
2
3
| 输入: row = [0, 2, 1, 3]
输出: 1
解释: 我们只需要交换row[1]和row[2]的位置即可。
|
示例 2:
1
2
3
| 输入: row = [3, 2, 0, 1]
输出: 0
解释: 无需交换座位，所有的情侣都已经可以手牵手了。
|
并查集~
学过交换排序的肯定都知道，最多只需要 $n-1$ 次交换就能让长为 $n$ 的数组有序，用到这题同理，我们发现最多只需要 $\frac{n}{2}-1$ 次交换就可以让所有情侣配对，那么怎么计算最少交换次数呢？
这里就要用到并查集了，我们考虑每一对情侣就是一个连通分量，最后配对之后的连通分量就是 $\frac{n}{2}$ 对，那么我们只需要计算出开始的连通分量个数 $cnt$，答案就是 $\frac{n}{2}-cnt$ 了，因为每一个配对的情侣编号都是一奇一偶，所以我们可以除 $2$ 来将编号统一，AC代码如下：
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
34
35
36
37
38
| class Unionset {
public:
vector<int> father;
vector<int> sum;
int cnt = 0;
public:
void init(int n) {
father.resize(n);
for (int i = 0; i < n; i++) father[i] = i;
sum.resize(n);
cnt = n;
}
int findFather(int x) {
return x == father[x] ? x : father[x] = findFather(father[x]);
}
bool Union(int x, int y) {
x = findFather(x), y = findFather(y);
if (x == y) return 0;
if (sum[x] < sum[y]) swap(x, y);
father[y] = x;
sum[x] += sum[y];
--cnt;
return 1;
}
};
class Solution {
public:
int minSwapsCouples(vector<int> &row) {
int n = row.size();
Unionset u = Unionset();
u.init(n / 2);
for (int i = 0; i < n; i += 2) u.Union(row[i] / 2, row[i + 1] / 2);
return n / 2 - u.cnt;
}
};
|