题目

首先，我们总是以「情侣对」为单位进行设想：

• 当有两对情侣相互坐错了位置，ta们两对之间形成了一个环。需要进行一次交换，使得每队情侣独立（相互牵手）

• 如果三对情侣相互坐错了位置，ta们三对之间形成了一个环，需要进行两次交换，使得每队情侣独立（相互牵手）

• 如果四对情侣相互坐错了位置，ta们四对之间形成了一个环，需要进行三次交换，使得每队情侣独立（相互牵手）

也就是说，如果我们有 k 对情侣形成了错误环，需要交换 k - 1 次才能让情侣牵手。

java
 class Solution {
    int[] p = new int[70];
    void union(int a, int b) {
        p[find(a)] = p[find(b)];
    }
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    public int minSwapsCouples(int[] row) {
        int n = row.length, m = n / 2;
        for (int i = 0; i < m; i++) p[i] = i;
        for (int i = 0; i < n; i += 2) union(row[i] / 2, row[i + 1] / 2);
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            if (i == find(i)) cnt++;
        }
        return m - cnt;
    }
}

贪心的做法就比较简单，从前往后遍历 row 数组，如果 i < row.length - 1 && row[i] 和 row[i + 1] 能够成功牵手，那么我们跳过这对情侣，执行 i += 2；否则我们就从 i + 1 出发，遍历 row 数组，寻找能与 row[i] 牵手的 row[j] ，交换 row[i + 1] 和 row[j] 并更新交换次数 ans，再 i += 2， 重复上述过程直至完成遍历。

java
class Solution {
    // 贪心解法
    public int minSwapsCouples(int[] row) {
        int ans = 0, n = row.length;
        for (int i = 0; i < n; i++) {
            if (i < n - 1 && (row[i] ^ row[i + 1]) == 1) {
                i++;
                continue;
            }
            for (int j = i + 1; j < n; j++) {
                if ((row[j] ^ row[i]) == 1) {
                    int t = row[i + 1];
                    row[++i] = row[j];
                    row[j] = t;
                    ans++;
                    break;
                }
            }
        }
        return ans;
    }
}