LeetCode 765. 情侣牵手

约 5 分钟
文章信息 6 个分类 5 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 字节
标签
深度优先搜索 广度优先搜索 贪心 图 并查集

题目描述

✅ 765. 情侣牵手

image-20260929104719074

image-20260929104719201

题意分析

每对情侣需要坐在相邻的固定座位组中，一次可以交换任意两人的位置，求最少交换次数。

解法：贪心 + 位置映射

核心思路

[!blue]

从左到右处理每组两个座位，固定左边的人 a，把伴侣换到右边。情侣编号分别是偶数及紧接着的奇数，最低位不同，其余位相同，所以伴侣编号为 p = a ^ 1。用 pos[value] 记录每个人当前坐在哪里，就能直接找到 p 的位置。

若右边已经是 p，这一组无需交换；否则把右边的 b 与位置 pos[p] 上的 p 互换，并同时更新两人的位置记录。之前处理好的座位组都是完整情侣，不可能包含当前 a 的伴侣，因此这次交换不会破坏已完成的前缀。

最少交换次数可以由配对关系证明。把每对情侣看作一个节点，每组座位连一条边，连接坐在这组座位上的两人所属的情侣。每对情侣的两个人分别占一个座位，所以每个节点度数为 2，连通分量都是环；已经配对的一组对应单节点自环。

一个包含 c 对情侣的环，最终要拆成 c 个独立自环。交换两个人只会重新连接涉及的两条边，最多把一个环拆成两个环，也就是让连通分量数增加 1，因此至少需要 c-1 次交换。

贪心每次把 a 与伴侣放到同一组，就从所在环中单独拆出这一对，剩余情侣继续形成一个更小的环。每次交换恰好让分量数增加 1，直到全部配对，所以每个环正好使用 c-1 次，达到下界。这也解释了为什么一次交换可能同时修好两组，不能用“每次只修好一组”证明最优性。

解题步骤

  1. 建立每个人到当前位置的索引。
  2. 每次处理下标 i、i+1 组成的座位组。
  3. 若右边不是左边的伴侣，则找到伴侣位置并交换。
  4. 同步更新被交换两人的位置，累计交换次数。

代码实现

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 为座位数组长度，建立位置表并逐组处理，每组至多交换一次。
  • 空间复杂度：$O(n)$，位置表；座位数组会原地修改。

关键点总结

[!green]

  • 先固定一组，后续无需再动已完成的座位组。
  • 位置映射与数组必须保持一致，才能继续常数时间找人。
  • 一次交换可能同时修好两组，不能用错配人数简单除二推答案。

易错点总结

[!yellow]

  • 用 x+1 统一计算伴侣：奇数编号的伴侣是前一个偶数。
  • 交换后只更新伴侣的位置：被换走的另一人也改变了位置，两条记录必须同步维护。
  • 按相邻交换次数计费：题目允许任意两人直接交换。
  • 每组只前进一个下标：破坏固定的两座位分组。

相似题目

题目 难度 关联与区别
补充题 101. 数组排序的最少交换次数 困难 同样通过交换拆解错位形成的连通结构，长度为L的关联环通常贡献L-1次交换。
1202. 交换字符串中的元素 中等 同样利用交换关系形成的连通分量，本题分量决定需要几次配对修复，原题分量内重排字符。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/65584602
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！