谷歌云可以做网站吗,选择一个域名进行网站建设,成都学生网站制作,有做销售产品的网站有哪些内容N 对情侣坐在连续排列的 2N 个座位上#xff0c;想要牵到对方的手。 计算最少交换座位的次数#xff0c;以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人#xff0c;让他们站起来交换座位。
人和座位用 0 到 2N-1 的整数表示#xff0c;情侣们按顺序编号#xff…N 对情侣坐在连续排列的 2N 个座位上想要牵到对方的手。 计算最少交换座位的次数以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人让他们站起来交换座位。
人和座位用 0 到 2N-1 的整数表示情侣们按顺序编号第一对是 (0, 1)第二对是 (2, 3)以此类推最后一对是 (2N-2, 2N-1)。
这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。
示例 1:
输入: row [0, 2, 1, 3] 输出: 1 解释: 我们只需要交换row[1]和row[2]的位置即可。
解题思路
将相邻的位置看成一条边使用并查集维护连通性最后构成的是拥有若干个环的图一个环代表需要在环内部需要交换位置的若干对情侣环内交换位置的开销为情侣对数减一举例子可以推导出所以对于所有的环来说总的开销为情侣对数-1X 环的个数情侣总对数-环的个数情侣总对数-连通分量
代码
class Solution {public int minSwapsCouples(int[] row) {int lenrow.length,nlen/2;union union new union(n);//将同一对情侣看成是一个节点union.init();for (int i 0; i len; i2) {union.union(row[i]/2,row[i1]/2);}return n-union.n;}class union{int[] fa;int n;public union(int n) {fanew int[n];this.n n;}public void init(){for(int i0;ifa.length;i)fa[i]i;}public int find(int x){if(x!fa[x])fa[x]find(fa[x]);return fa[x];}public void union(int x,int y){xfind(x);yfind(y);if(xy) return;fa[x]y;n--;}}
}
