【每日一题】情侣牵手

牵手"/>

【每日一题】情侣牵手

文章目录

• 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_1, N_2, ..., N_n N1​,N2​,...,Nn​ 对，n 即为并查集里连通分量的个数，并且 N 1 + N 2 + . . . + N n = N N_1 + N_2 + ... + N_n = N N1​+N2​+...+Nn​=N。把所有连通分量中的交换正确的坐在一起，每一个连通分量至少要 N 1 − 1 , N 2 − 1 , . . . , N n − 1 N_1-1, N_2-1, ..., N_n-1 N1​−1,N2​−1,...,Nn​−1 次。这种规律对于初始的时候已经坐在一起的情侣同样成立，因为已经坐在一起的情侣在并查集里成为一个连通分量，无须交换，此时 1 − 1 = 0 1 - 1 = 0 1−1=0。综上所述，让所有的情侣都能牵手至少须要交换的次数为：

( N 1 − 1 ) + ( N 2 − 1 ) + . . . + ( N n − 1 ) = N − n (N_1-1) + (N_2-1) + ... + (N_n-1) = N - n (N1​−1)+(N2​−1)+...+(Nn​−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;}
};

复杂度分析

时间复杂度： O ( m l o g m ) O(mlogm) O(mlogm)， m m m 为数组 row 长度的一半。

空间复杂度： O ( l o g m ) O(logm) O(logm)。

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。