题目

题目来源：力扣（LeetCode）

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]的位置即可。

示例 2:

输入: row = [3, 2, 0, 1]
输出: 0
解释: 无需交换座位，所有的情侣都已经可以手牵手了。

思路分析

情侣们按顺序编号，如果一对情侣恰好坐在了一起，并且坐在了成组的座位上，其中一个下标一定是偶数，另一个一定是奇数，并且 「偶数 + 1 = 奇数」。例如编号数对 [2, 3]、[9， 8]，这些数对的特点是：编号除以 2 (下取整) 得到的数相等。

我们遍历 row 数组，每次取出两个人，如果这两个人的编号除以2后向下取整得到的数相等，那么这两个人必定是情侣，此时无需调整。如果两人的编号除以2向下取整的结果不相等，则将结果进行连通，然后进行交换调整。当 N - 1 对情侣交换配对成功的时候，最后一对情侣也会配对成功。

因此，我们只需要记录连通分量的个数就可以得到交换的次数：「至少交换的次数 = 所有情侣的对数 - 并查集里连通分量的个数」。

  1. /**
  2.  * @param {number[]} row
  3.  * @return {number}
  4.  */
  5. var minSwapsCouples = function (row) {
  6.   const len = row.length;//获取情侣的数量
  7.   // 获取情侣的对数
  8.   let N = len >> 1;// 右移1位 相等于除以2；
  9.   // 以情侣的对数构建并查集
  10.   let uf = new UnionFind(N);
  11.   for (let i = 0; i < len; i += 2) {//跳着循环，每次取两个值；
  12.     // 拿到这两个人的编号除以2向下取整，将得到的数进行连通；
  13.     // 右移一位，相当于是除以 2 ，并且是整除(相当于是向下取整)
  14.     uf.unite(row[i] >> 1, row[i + 1] >> 1);
  15.   }
  16.   return N - uf.getCount(); // 至少交换的次数 = 情侣的对数 - 并查集里连通分量的个数
  17. };
  19. // 并查集
  20. class UnionFind {
  21.   constructor(n) {
  22.     // 元素所指向的父节点，parent[i] 表示第 i 个元素所指向的父节点
  23.     // 初始化时, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
  24.     this.parent = new Array(n).fill(0).map((value, index) => index);
  25.     // 树的层数，rank[i] 表示以 i 为根的集合所表示的树的层数
  26.     this.rank = new Array(n).fill(1);
  27.     // 节点的个数
  28.     this.setCount = n;
  29.   }
  31.   // 查找过程，查找元素 index 所在集合的编号(查找树的根节点)
  32.   findSet(index) {
  33.     // 不断去查询自己的父节点，直至根节点
  34.     // 根节点的标志是父节点就是本身  parent[index] == index
  35.     if (this.parent[index] != index) {
  36.       // 递归获取节点的父节点
  37.       this.parent[index] = this.findSet(this.parent[index]);
  38.     }
  39.     // 返回根节点
  40.     return this.parent[index];
  41.   }
  43.   // 合并两个集合
  44.   unite(index1, index2) {
  45.     let root1 = this.findSet(index1);
  46.     let root2 = this.findSet(index2);
  47.     // 根节点不一样，是两个不同的集合(两棵不同的树)
  48.     if (root1 != root2) {
  49.       // 根据树的层数合并集合
  50.       // 
  51.       if (this.rank[root1] < this.rank[root2]) {
  52.         // 这个判断如果 root2 所在树的层数 大于 root1，就交换两个父节点，这样始终让 root1 为父节点
  53.         [root1, root2] = [root2, root1];
  54.       }
  55.       // 将层数多的集合合并到集合少的集合
  56.       this.parent[root2] = root1;
  57.       this.rank[root1] += this.rank[root2];
  58.       this.setCount--;
  59.     }
  60.   }
  62.   getCount() {
  63.     return this.setCount;
  64.   }
  66.   connected(index1, index2) {
  67.     return this.findSet(index1) === this.findSet(index2);
  68.   }
  69. }