【每日一题】情侣牵手

文章目录

Tag
题目来源
题目解读
解题思路
- 方法一：并查集
写在最后

Tag

【并查集】【数组】【2023-11-11】

题目来源

765. 情侣牵手

题目解读

返回最少的交换座位的次数，使每对情侣可以坐在一起。

解题思路

方法一：并查集

对于一对情侣，有两个座位，无需交换，ta们就可以坐在一起。

对于两对情侣，如果ta们坐错了位置，那么至少需要交换 1 次才能正确的坐在一起。ta们坐错了位置其实就是出现了首尾相连的情况。

对于三对情侣，如果ta们坐错了位置，那么至少需要交换 2 次才能正确的坐在一起。ta们坐错了位置其实就是出现了首尾相连的情况。

如果对于 n 对情侣，那么至少需要交换 n-1 次才能正确的坐在一起。

首尾相连的情况就是一个连通分量，我们可以通过【并查集】将首尾相连的情侣连接在一起形成一个连通分量，也可以通过【并查集】的方法统计交换之前有 cnt 个连通分量。

假设一共有 N 对情侣，形同连通分量的情侣（包括坐错位置和坐对位置的情况）有 $N_1, N_2, ..., N_n$ 对，n 即为并查集里连通分量的个数，并且 $N_1 + N_2 + ... + N_n = N$ 。把所有连通分量中的交换正确的坐在一起，每一个连通分量至少要 $N_1-1, N_2-1, ..., N_n-1$ 次。这种规律对于初始的时候已经坐在一起的情侣同样成立，因为已经坐在一起的情侣在并查集里成为一个连通分量，无须交换，此时 $1 - 1 = 0$ 。综上所述，让所有的情侣都能牵手至少须要交换的次数为：

$N_1-1) + (N_2-1) + ... + (N_n-1) = N - n$

在代码中统计合并之后的 i == find(i) 的个数，即为连通分量的个数。

实现代码

class Solution {
public:
    int parent[70];

    void union1(int a, int b) {
        parent[find(a)] = parent[find(b)];
    }

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

    int minSwapsCouples(vector<int>& row) {
        int n = row.size(), m = n / 2;
        for (int i = 0; i < m; ++i) {
            parent[i] = i;
        }
        for (int i = 0; i < n; i += 2) {
            union1(row[i] / 2, row[i+1] / 2);
        }
        int res = 0;
        for (int i = 0; i < m; ++i) {
            if (i == find(i)) {
                ++res;
            }
        }
        return m - res;
    }
};