Hard

题目描述

有 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
  • 0 <= row[i] < 2n
  • row 中所有元素均不相同

解题思路

这道题可以用图论的思路来解决，将其转化为寻找图中连通分量的问题。

核心思路： 将每个沙发（两个相邻座位）看作一个节点。如果一对情侣分别坐在不同的沙发上，就在这两个沙发之间连一条边。这样就构成了一个图。

关键观察：

  • 每个连通分量中如果有 k 个节点（沙发），那么需要 k-1 次交换才能让这个连通分量中的所有情侣都坐到一起
  • 总的交换次数就是所有连通分量的 (节点数-1) 之和

算法步骤：

  1. 遍历每个沙发（每两个相邻座位），检查坐在上面的两个人是否为情侣
  2. 如果不是情侣，就在对应的沙发之间建立连边关系
  3. 使用并查集或DFS找出所有连通分量
  4. 计算每个连通分量需要的交换次数并累加

贪心解法（推荐）： 也可以用更直接的贪心方法：从左到右遍历每个沙发，如果当前沙发上的两个人不是情侣，就找到其中一个人的伴侣，与另一个位置的人交换。

代码实现

class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        int n = row.size() / 2;
        vector<int> parent(n);
        
        // 初始化并查集
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        function<int(int)> find = [&](int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        };
        
        auto unite = [&](int x, int y) {
            int px = find(x), py = find(y);
            if (px != py) {
                parent[px] = py;
            }
        };
        
        // 建立连通关系
        for (int i = 0; i < row.size(); i += 2) {
            int couch1 = row[i] / 2;    // 第一个人所属的情侣组
            int couch2 = row[i + 1] / 2;  // 第二个人所属的情侣组
            unite(couch1, couch2);
        }
        
        // 统计连通分量
        unordered_map<int, int> groups;
        for (int i = 0; i < n; i++) {
            groups[find(i)]++;
        }
        
        int swaps = 0;
        for (auto& [root, size] : groups) {
            swaps += size - 1;
        }
        
        return swaps;
    }
};

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        n = len(row) // 2
        parent = list(range(n))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            px, py = find(x), find(y)
            if px != py:
                parent[px] = py
        
        # 建立连通关系
        for i in range(0, len(row), 2):
            couch1 = row[i] // 2     # 第一个人所属的情侣组
            couch2 = row[i + 1] // 2   # 第二个人所属的情侣组
            union(couch1, couch2)
        
        # 统计连通分量
        from collections import defaultdict
        groups = defaultdict(int)
        for i in range(n):
            groups[find(i)] += 1
        
        # 计算总交换次数
        swaps = 0
        for size in groups.values():
            swaps += size - 1
        
        return swaps

public class Solution {
    public int MinSwapsCouples(int[] row) {
        int n = row.Length / 2;
        int[] parent = new int[n];
        
        // 初始化并查集
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        int Find(int x) {
            if (parent[x] != x) {
                parent[x] = Find(parent[x]);
            }
            return parent[x];
        }
        
        void Union(int x, int y) {
            int px = Find(x), py = Find(y);
            if (px != py) {
                parent[px] = py;
            }
        }
        
        // 建立连通关系
        for (int i = 0; i < row.Length; i += 2) {
            int couch1 = row[i] / 2;      // 第一个人所属的情侣组
            int couch2 = row[i + 1] / 2;  // 第二个人所属的情侣组
            Union(couch1, couch2);
        }
        
        // 统计连通分量
        Dictionary<int, int> groups = new Dictionary<int, int>();
        for (int i = 0; i < n; i++) {
            int root = Find(i);
            groups[root] = groups.GetValueOrDefault(root, 0) + 1;
        }
        
        int swaps = 0;
        foreach (var size in groups.Values) {
            swaps += size - 1;
        }
        
        return swaps;
    }
}

var minSwapsCouples = function(row) {
    const n = row.length / 2;
    const parent = Array.from({length: n}, (_, i) => i);
    
    function find(x) {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    function union(x, y) {
        const px = find(x), py = find(y);
        if (px !== py) {
            parent[px] = py;
        }
    }
    
    // 建立连通关系
    for (let i = 0; i < row.length; i += 2) {
        const couch1 = Math.floor(row[i] / 2);     // 第一个人所属的情侣组
        const couch2 = Math.floor(row[i + 1] / 2); // 第二个人所属的情侣组
        union(couch1, couch2);
    }
    
    // 统计连通分量
    const groups = new Map();
    for (let i = 0; i < n; i++) {
        const root = find(i);
        groups.set(root, (groups.get(root) || 0) + 1);
    }
    
    let swaps = 0;
    for (const size of groups.values()) {
        swaps += size - 1;
    }
    
    return swaps;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型并查集解法
时间复杂度O(n·α(n))
空间复杂度O(n)

其中 n 是情侣对数，α(n) 是阿克曼函数的反函数，在实际应用中可以看作常数。

相关题目