LeetCode 765. 情侣牵手

2021-03-25 HGNULB 约 14 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 765. 情侣牵手

题意分析

$n$ 对情侣坐在 $2n$ 个连成一排的座位上，row[i] 表示第 $i$ 个座位上坐的人的编号。编号规则是固定的：第 $k$ 对情侣的编号是 $2k$ 和 $2k+1$。每次操作可以让任意两个人交换座位，问最少交换多少次，才能让每一对情侣都并排坐在一起。

「并排坐在一起」需要读准：座位是按 $(0,1)$、$(2,3)$、$(4,5)$ 这样两两成组的，情侣必须占满同一组的两个座位，而不是「相邻下标」那么宽松。所以 0 号和 1 号情侣坐在座位 1 和 2 是不算成功的——那跨了两个组。这决定了整个算法以「座位对」为单位而不是以单个座位为单位。

编号规则给了一个极其好用的性质：$2k$ 与 $2k+1$ 只差最低位，所以某人 $x$ 的伴侣恒等于 $x \oplus 1$。偶数异或 1 加一变奇数，奇数异或 1 减一变偶数，一个运算覆盖两种情况，不需要判断奇偶。看到「$2k$ 与 $2k+1$ 配对」这种编号约定，就应该条件反射地想到异或最低位。

约束方面：row 是 $0$ 到 $2n-1$ 的一个排列（每个人恰好出现一次），$1 \le n \le 30$。数据规模小到几乎任何做法都能过，所以题目考的不是效率而是最优性论证——你得说清楚为什么你的交换次数是最少的，而不是仅仅让所有情侣坐到一起。

「排列」这个性质还有一个实用推论：可以用一个长度为 $2n$ 的数组做「人 → 座位」的反向索引，因为编号本身就是稠密的下标。这比用哈希表更省更快。

边界方面：已经全部排好时答案为 0；只有一对情侣时答案必然是 0（两个人无论怎么坐都在同一组）。这些应由主流程自然得出。

解法：贪心 + 位置映射

核心思路

暴力做法是把「座位排列」当作状态做广度优先搜索，每次枚举一对人交换，找到目标状态的最短路。状态空间是 $(2n)!$，$n = 30$ 时天文数字，完全不可行。瓶颈很清楚：我们在盲目地搜索所有交换，而实际上每一次有效的交换都应该至少让一对情侣就位，不该存在「先把局面搅乱再理顺」的中间步骤。

顺着这个直觉走：从左到右逐个处理座位对。看第 $i$ 组（座位 $i$ 和 $i+1$，$i$ 是偶数），如果 row[i+1] 恰好是 row[i] 的伴侣，这一组已经完成，直接跳过；否则，把 row[i] 的伴侣从他当前所在的座位直接换到座位 $i+1$。一次交换，这一组永久固定，此后再也不动。

关键在于论证「这样做的总次数是最少的」。把每个座位对看成图中的一个节点，共 $n$ 个节点；对每一对情侣，如果他俩分别坐在座位对 $u$ 和座位对 $v$ 上（$u \ne v$），就在 $u$ 与 $v$ 之间连一条边；如果他俩已在同一对座位上，这条边是自环，可以忽略。由于每个座位对恰好坐两个人、每个人恰好属于一对情侣，这个图里每个节点的度数是固定的，整张图会分解成若干个连通分量。

现在看一个含 $k$ 个座位对的连通分量。分量内部的人只会与分量内部的人配对，所以它可以独立处理。一个大小为 $k$ 的分量恰好需要 $k-1$ 次交换：下界方面，每次交换最多让图中减少一条「跨座位对」的边，也就是最多让分量的连通块数增加一个，要把 $k$ 个节点全部拆成 $k$ 个自环闭合的独立单元，至少需要 $k-1$ 次；上界方面，上面的贪心过程每次交换都恰好固定一个座位对并把分量规模减一，$k-1$ 次后必然全部就位。上下界重合，所以答案就是 $n$ 减去连通分量个数，而贪心正好达到这个值。

明确一下贪心过程中维持的不变量：处理完前 $i/2$ 个座位对后，这些座位对里坐的都是完整的情侣，且它们此后不会再被任何交换触碰。第二个半句是正确性的要害——交换发生在 座位 i+1 与「伴侣当前所在的座位 $j$」之间，而 $j$ 一定大于 $i+1$（因为前面的座位都已锁定且里面的人都已配对），所以已完成的部分不会被破坏。

最后一个技术点：如何 $O(1)$ 找到伴侣当前坐在哪。因为编号是 $0$ 到 $2n-1$ 的排列，直接开一个数组 $pos$，令 $pos[v]$ 等于人 $v$ 所在的座位下标即可。每次交换后必须同步更新两个人的 $pos$，否则索引与实际座位脱节，后续查找会指向错误的位置。

解题步骤

第一步，扫一遍 row 建立反向索引 $pos$，令 $pos[row[i]] = i$。 为什么可以用数组而不是哈希表：row 是 $0$ 到 $2n-1$ 的排列，编号本身就是稠密的合法下标，数组既省内存又是真正的 $O(1)$。

第二步，令 $answer = 0$，以步长 2 遍历座位下标 $i$。 为什么步长是 2：题目按 $(0,1)$、$(2,3)$ 分组，处理单位是「座位对」而不是「座位」。步长写成 1 会把同一组处理两遍，第二遍时组内已配对，虽不至于出错但纯属浪费；更危险的是从奇数下标开始会跨组配对，答案彻底错误。

第三步，取 $a = row[i]$，算出伴侣 $p = a \oplus 1$。 为什么以左座位的人为基准去找伴侣，而不是反过来：两种选法都可行，但必须固定一种。固定以左座位为基准，交换的目标位置就恒为 $i+1$，逻辑最简。

第四步，若 $row[i+1] = p$，这一组已完成，跳过。 为什么不需要额外记录「已完成」的标记：处理是严格从左到右且已完成的组不会被后续交换触碰，位置本身就是最好的标记。

第五步，否则取 $j = pos[p]$（伴侣当前座位）、$b = row[i+1]$（当前占着目标座位的人），执行 $row[i+1] \leftarrow p$、$row[j] \leftarrow b$。 为什么是「把伴侣换过来」而不是「把 $row[i]$ 换到伴侣旁边」：后者会破坏已经锁定的左半部分，因为 $row[i]$ 所在的位置属于当前正在固定的组。

第六步，同步更新 $pos[p] \leftarrow i+1$、$pos[b] \leftarrow j$，并令 $answer$ 加一。 为什么必须同步更新：$pos$ 是 row 的镜像，任何一次对 row 的写入都要在 $pos$ 上有对应的写入。漏更新会让后续的 $pos$ 查询返回旧座位，交换到错误的人身上，答案偏大甚至陷入错乱。

第七步，遍历结束返回 $answer$。

以 row = [0, 2, 4, 1, 3, 5]（三对情侣）走一遍。伴侣关系是 $(0,1)$、$(2,3)$、$(4,5)$，座位对是 $(0,1)$、$(2,3)$、$(4,5)$。

初始 $pos$：人 0 在座位 0，人 2 在座位 1，人 4 在座位 2，人 1 在座位 3，人 3 在座位 4，人 5 在座位 5。

先用连通分量的视角预判答案：座位对 0 坐着 ${0, 2}$，座位对 1 坐着 ${4, 1}$，座位对 2 坐着 ${3, 5}$。情侣 $(0,1)$ 跨座位对 0 与 1，情侣 $(2,3)$ 跨座位对 0 与 2，情侣 $(4,5)$ 跨座位对 1 与 2。三个节点由三条边连成一个环，只有 1 个连通分量，所以答案应为 $3 - 1 = 2$。

$i = 0$：$a = row[0] = 0$，伴侣 $p = 0 \oplus 1 = 1$。$row[1] = 2 \ne 1$，需要交换。$j = pos[1] = 3$，$b = row[1] = 2$。执行 $row[1] \leftarrow 1$、$row[3] \leftarrow 2$，序列变为 [0, 1, 4, 2, 3, 5]。更新 $pos[1] \leftarrow 1$、$pos[2] \leftarrow 3$。$answer = 1$。座位对 0 完成，此后永不触碰。

$i = 2$：$a = row[2] = 4$，伴侣 $p = 5$。$row[3] = 2 \ne 5$，需要交换。$j = pos[5] = 5$，$b = row[3] = 2$。执行 $row[3] \leftarrow 5$、$row[5] \leftarrow 2$，序列变为 [0, 1, 4, 5, 3, 2]。更新 $pos[5] \leftarrow 3$、$pos[2] \leftarrow 5$。$answer = 2$。注意这次交换的目标座位 $j = 5$ 严格大于 $i+1 = 3$，验证了「不会破坏已锁定部分」这条不变量。

$i = 4$：$a = row[4] = 3$，伴侣 $p = 3 \oplus 1 = 2$。$row[5] = 2$，恰好相等，跳过。这一步体现了贪心的收尾特性——处理完前 $n-1$ 个座位对后，最后一对必然自动成立，因为剩下的两个人只能是彼此的伴侣。

返回 2，与连通分量的预判一致。整个过程只做了 2 次交换，每次都固定了一个座位对，没有任何一次交换是「白做」的。

再看一个不需要交换的例子 row = [3, 2, 0, 1]：$i = 0$ 时 $a = 3$、$p = 2$，$row[1] = 2$ 相等，跳过；$i = 2$ 时 $a = 0$、$p = 1$，$row[3] = 1$ 相等，跳过。返回 0。这说明情侣的左右顺序无关紧要——$3$ 坐左边、$2$ 坐右边同样算牵手成功，异或判断天然覆盖了两种顺序。

代码实现

class Solution {
    public int minSwapsCouples(int[] row) {
        int n = row.length;
        int[] pos = new int[n];
        for (int i = 0; i < n; i++) {
            pos[row[i]] = i;
        }

        int answer = 0;
        for (int i = 0; i < n; i += 2) {
            int a = row[i];
            int p = a ^ 1;
            if (row[i + 1] == p) {
                continue;
            }

            int j = pos[p];
            int b = row[i + 1];

            row[i + 1] = p;
            row[j] = b;

            pos[p] = i + 1;
            pos[b] = j;
            answer++;
        }

        return answer;
    }
}

func minSwapsCouples(row []int) int {
    n := len(row)
    pos := make([]int, n)
    for i, v := range row {
        pos[v] = i
    }

    answer := 0
    for i := 0; i < n; i += 2 {
        a := row[i]
        p := a ^ 1
        if row[i+1] == p {
            continue
        }

        j := pos[p]
        b := row[i+1]

        row[i+1] = p
        row[j] = b
        pos[p] = i + 1
        pos[b] = j
        answer++
    }

    return answer
}

复杂度分析

时间复杂度：$O(n)$，$n$ 为座位总数 $2 \times$ 情侣对数。建立反向索引扫一遍是 $O(n)$；主循环以步长 2 走过全部座位，每组内部只做常数次数组读写和一次异或，没有任何查找或嵌套循环。相比并查集写法省掉了 $\alpha(n)$ 的路径压缩开销，是本题的最优解法。

空间复杂度：$O(n)$，唯一的额外结构是长度为 $n$ 的反向索引数组。row 是原地修改的，不额外占空间；如果题目不允许修改入参，需要先拷贝一份，空间仍是 $O(n)$。

关键点总结

成对编号看到就想异或最低位。$2k$ 与 $2k+1$ 互为伴侣等价于 $x$ 与 $x \oplus 1$ 互为伴侣，一个运算同时处理奇偶两种情况，比 x % 2 == 0 ? x + 1 : x - 1 更短也更不容易写反。这个技巧在线段树的兄弟节点、二进制配对、双缓冲切换里同样适用。

「最少操作数」类贪心必须给出下界论证。让所有情侣坐到一起很容易，难的是证明次数最少。本题的标准论证是转成图：座位对为节点、情侣为边，答案等于 $n$ 减连通分量数，因为每次交换最多让分量数加一。遇到「最少交换」「最少操作」的题，先找一个每次操作只能改变 1 的单调量，下界立刻浮现。

从左到右固定 + 锁定不回头，是原地重排类题目的通用骨架。核心是保证每次操作的作用范围严格落在「尚未处理」的后缀里，这样已完成的前缀就成了天然的不变量。判断标准很简单：交换的目标下标是否总是大于当前边界。

反向索引必须与主数组同步维护。$pos$ 与 row 是一份数据的两个视角，任何单边更新都会造成状态撕裂。写这类代码时把「改 row 的两行」和「改 $pos$ 的两行」紧挨着放，形成视觉上的成对结构，能显著降低漏更新的概率。

稠密整数键就用数组，不要用哈希表。row 是 $0$ 到 $2n-1$ 的排列这一条约束，直接决定了反向索引可以是数组。识别出「键是稠密下标」能省掉哈希的常数和空间开销。

面试视角：面试官通常会先让你写出贪心，然后追问「凭什么最少」。此时不要复述代码，而要画出座位对为节点的图，指出答案是 $n$ 减连通分量数，并说明每次交换最多让分量数加一给出了下界。如果面试官要求换一种解法，就给并查集版本：遍历每个座位对，把两个人所属的情侣编号 $row[i]/2$ 与 $row[i+1]/2$ 合并，最后答案是 $n$ 减去连通分量数——这个写法更直接地体现了上述论证，但常数略大。能同时给出两种并说清它们是同一个论证的两种落地方式，是这题的满分答案。

易错点总结

错误写法：循环步长写成 1。以 row = [0, 2, 1, 3] 为例，$i = 1$ 时会以座位 1 和座位 2 为一组去配对（人 2 与人 1），把本不该动的人换来换去，最终返回 2 甚至更大，而正确答案是 1。座位分组是 $(0,1)$、$(2,3)$，绝不能滑动。

错误写法：交换后忘记更新 $pos$。以 row = [0, 2, 4, 1, 3, 5] 为例，$i = 0$ 时把人 1 换到座位 1、人 2 换到座位 3，若不更新，$pos[2]$ 仍是 1；$i = 4$ 时 $a = 3$、$p = 2$，$row[5]$ 本已是 2 应当跳过，但若中途某步依赖了过期的 $pos[2] = 1$ 去交换，会把已锁定的座位对 0 破坏掉，返回 3 而正确答案是 2。

错误写法：只更新被移入者的 $pos$，漏掉被移走者。以 row = [0, 2, 4, 1, 3, 5] 为例，$i = 0$ 时更新了 $pos[1] = 1$ 却没更新 $pos[2] = 3$；$i = 2$ 时若需要查找人 2 的位置，会拿到旧值 1，交换写到座位 1 上，直接破坏已完成的第一组，结果错误且难以定位。两个人的位置必须同时更新。

错误写法：把 $row[i]$ 换到伴侣旁边，而不是把伴侣换到 $row[i]$ 旁边。以 row = [0, 2, 4, 1, 3, 5] 为例，$i = 0$ 时人 0 的伴侣 1 在座位 3，若把人 0 换到座位 2（座位对 1 的左位）去凑，座位对 0 反而被破坏，处理边界不再单调右移，循环可能永远无法收敛，最终返回值大于最优。

错误写法：用 x % 2 == 0 ? x + 1 : x - 1 求伴侣但写反了分支。以 row = [1, 0] 为例，人 1 是奇数应得伴侣 0，写反后得到 2，而 2 根本不在座位上，$pos[2]$ 读到的是未初始化的 0，交换会把座位 0 上的人搬走，返回 1 而正确答案是 0。异或写法从根本上消除了这个分支。

错误写法：把「情侣」判断成 row[i] + 1 == row[i+1]。以 row = [3, 2, 0, 1] 为例，第一组是人 3 和人 2，虽然是合法情侣但 $3 + 1 \ne 2$，被误判为需要交换，返回 1 甚至更多，而正确答案是 0。情侣不区分左右顺序，必须用异或或除以 2 相等来判断。

错误写法：以为每次交换固定的是「一个人」而不是「一对座位」，于是把答案累加两次。以 row = [0, 2, 1, 3] 为例，一次交换同时把人 1 和人 2 放到了正确的位置，若按「移动了两个人」计数会返回 2，而正确答案是 1。

错误写法：用并查集但按「人」而不是按「情侣编号」建图。以 row = [0, 2, 4, 1, 3, 5] 为例，若把每个座位对里的两个人合并，会得到 6 个人分成若干组，用 $2n$ 减分量数算出的值与真实答案无关。正确的建图是把 $row[i]/2$ 与 $row[i+1]/2$（即两人所属的情侣编号）合并，答案是 $n$ 减分量数。

错误写法：读取 $b = row[i+1]$ 放在 $row[i+1] \leftarrow p$ 之后。以任意需要交换的输入为例，此时 $b$ 拿到的已经是刚写入的伴侣编号 $p$，随后 $row[j] \leftarrow b$ 会让 $p$ 同时出现在两个座位上，排列被破坏，后续 $pos$ 查询全部失效。先读后写的顺序不可颠倒。

错误写法：$pos$ 数组按座位数开成 $n/2$ 长度。以 $n = 4$ 为例，人的编号最大是 3，$pos$ 必须能容纳下标 3，长度至少为 4；开成 2 会在 $pos[row[2]]$ 处越界，Java 抛数组越界异常，Go 直接 panic。$pos$ 的下标是人的编号，长度等于座位总数。

错误写法：跳过分支里仍然让 $answer$ 加一。以 row = [0, 1, 2, 3] 为例，全部已就位却返回 2，正确答案是 0。计数只应发生在真正执行了交换的分支里。

相似题目

题目	难度	考察点
41. 缺失的第一个正数	困难	同样是「把每个元素换到它该在的位置」的原地交换，但循环条件与终止判断更微妙
1202. 交换字符串中的元素	中等	交换关系构成连通分量后组内可任意重排，考察的是分量内排序而非分量计数
547. 省份数量	中等	并查集的裸题，邻接矩阵直接给出边，可用来熟悉「答案等于连通分量数」的模型
323. 无向图中连通分量的数目	中等	边表形式的连通分量计数，是本题图模型建立之后的最后一步
684. 冗余连接	中等	关注的是加边时首次成环的那条边，考察合并前的连通性判定
990. 等式方程的可满足性	中等	先合并所有等式再逐条校验不等式，训练「先建关系后判定」的两阶段套路
721. 账户合并	中等	需要把字符串映射成整数下标再并查集，多一层离散化
839. 相似字符串组	困难	边不是给定的而要 $O(n^2)$ 两两判定，重点在相似性判据的设计
面试题 17.07. 婴儿名字	中等	分量内还要选出字典序最小的代表并汇总频次，在连通分量上附加了聚合操作