AcWing 1224. 交换瓶子

思路：
方法1：图的方式找环，数组长度为n,找环的个数cnt，最终结果为n - cnt
方法2：连通块的方式找环

765. 情侣牵手

n 对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手。
人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n-2, 2n-1)。
返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起。 每次交换可选择任意两人，让他们站起来交换座位。

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

提示:

  • 2n == row.length
  • 2 <= n <= 30
  • n 是偶数
  • 0 <= row[i] < 2n
  • row 中所有元素均无重复

思路：
方法1：
转换成类似上一题的思路，选定偶数下标上的数作为基准，如果有两个偶数下标上的数本身能凑成一对，通过置换找到一个新数即可。通过映射将其转换为与上一题完全一致的模式然后找环

  1. class Solution {
  2.     public int minSwapsCouples(int[] row) {
  3.         int n = row.length, m = n / 2;
  4.         boolean[] st = new boolean[m];
  5.         int[] used = new int[m];
  6.         Arrays.fill(used, -1);
  7.         int[] a = new int[m], b = new int[m];
  8.         int[] map = new int[m];
  9.         int cnt = 0;
  10.         for (int i = 0; i < n; i++)
  11.             row[i] /= 2;
  13.         for (int i = 0, j = 0; i < n; j++, i += 2) {
  14.             while (used[row[i]] != -1) {
  15.                 cnt++;
  16.                 swap(row, i, used[row[i]] + 1);
  17.             }
  18.             used[row[i]] = i;
  19.             a[j] = row[i];
  20.             map[row[i]] = j;
  21.         }
  23.         for (int i = 1, j = 0; i < n; i += 2, j++) {
  24.             b[j] = map[row[i]];
  25.         }
  27.         for (int i = 0; i < m; i++) {
  28.             if (st[i] || b[i] == i) continue;
  29.             int x = b[i];
  30.             while (x != i) {
  31.                 st[x] = true;
  32.                 x = b[x];
  33.                 cnt++;
  34.             }
  35.         }
  36.         return cnt;
  38.     }
  39.     void swap(int[] a, int i, int j) {
  40.         int t = a[i];
  41.         a[i] = a[j];
  42.         a[j] = t;
  43.     }
  44. }
  1. 方法2：<br />并查集找连通块，如何merge？<br />首先对所有元素整除2，使得本应在同一座位上的两个元素大小一致<br />对于一个座位上的两个人，合并他们即可<br />最终结果就是总座位数 - 连通块数量