相信科学系列，两种 100% 解法背后的分析证明

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

这是 LeetCode 上的765. 情侣牵手，难度为 Hard。

$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

解释: 无需交换座位，所有的情侣都已经可以手牵手了。
复制代码

说明:

$len(row)$ 是偶数且数值在 $[4, 60]$ 范围内。
可以保证 row 是序列 $0…len(row)-1$ 的一个全排列。

并查集

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

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

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

于是问题转化成 $n / 2$ 对情侣中，有多少个这样的环。

可以直接使用「并查集」来做。

由于 0和1配对、2和3配对 … 因此互为情侣的两个编号除以 2 对应同一个数字，可直接作为它们的「情侣组」编号。

代码：

 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;
    }
}
复制代码

时间复杂度： $O(n)$
空间复杂度： $O(n)$

贪心算法

还是以「情侣对」为单位进行分析：

由于题目保证有解，我们也可以从前往后（每两格作为一步）处理，对于某一个位置而言，如果下一个位置不是应该出现的情侣的话。

则对下一个位置进行交换。

同时为了方便我们找到某个值的下标，需要先对 $row$ 进行预处理（可以使用哈希表或数组）。

代码：

class Solution {
    public int minSwapsCouples(int[] row) {
        int n = row.length;
        int ans = 0;
        int[] cache = new int[n];
        for (int i = 0; i < n; i++) cache[row[i]] = i;
        for (int i = 0; i < n - 1; i += 2) {
            int a = row[i], b = a ^ 1;
            if (row[i + 1] != b) {
                int src = i + 1, tar = cache[b];
                cache[row[tar]] = src;
                cache[row[src]] = tar;
                swap(row, src, tar);
                ans++;
            }
        }
        return ans;
    }
    void swap(int[] nums, int a, int b) {
        int c = nums[a];
        nums[a] = nums[b];
        nums[b] = c;
    }
}
复制代码