765.情侣牵手

【LetMeFly】765.情侣牵手：广度优先搜索BFS

力扣题目链接：https://leetcode.cn/problems/couples-holding-hands/

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
• n 是偶数
• 0 <= row[i] < 2n
• row 中所有元素均无重复

方法一：广度优先搜索BFS

首先我们可以把“0号1号”都看成“0号”、“2号3号”都看成“1号”、“4号5号”都看成“2号”、…、“$2n$号$2n+1$号”看成“$n$号”。

接下来讨论坐错的情况下，需要交换的次数：

• 假设一对情侣坐在一起(0, 0)，则需要交换$0$次
• 假设两对情侣坐错了(0, 1) (1, 0)，则需要交换$1$次
• 假设三对情侣坐错了(0, 1) (1, 2) (2, 0)，则需要交换$2$次
• …
• 假设n对情侣坐错了，则需要交换$n-1$次

因此我们的任务就是，将所有的人分成数个“循环情侣坐错环”。

怎么做呢？我们只需要建一张图，假设当前(0, 1)在一起，则在图中将点0和点1相连。

这样，我们只需要尝试从每个点开始广度优先搜索，就能得到每个子图的大小。每个子图的大小减一即为这个子图需要交换的次数。

座位情况：
3 3 0 1 1 2 4 5 2 0 4 5
--- --- --- --- --- ---

图的边：
3-3
0-1
1-2
4-5
2-0

子图：
3   0-1-2   4-5

需要交换次数：
(1-1) + (3-1) + (2-1) = 3

• 时间复杂度$O(len(row))$
• 空间复杂度$O(len(row))$

AC代码

C++

class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        int ans = 0;
        vector<vector<int>> graph(row.size() / 2);
        for (int i = 0; i < row.size(); i += 2) {
            graph[row[i] / 2].push_back(row[i + 1] / 2);
            graph[row[i + 1] / 2].push_back(row[i] / 2);
        }
        vector<bool> visited(row.size() / 2, false);
        queue<int> q;
        for (int i = 0; i < row.size() / 2; i++) {
            if (visited[i]) {
                continue;
            }
            q.push(i);
            visited[i] = true;
            int thisCnt = 0;
            while (q.size()) {
                thisCnt++;
                int thisPeople = q.front();
                q.pop();
                for (int nextPeople : graph[thisPeople]) {
                    if (!visited[nextPeople]) {
                        visited[nextPeople] = true;
                        q.push(nextPeople);
                    }
                }
            }
            ans += thisCnt - 1;
        }
        return ans;
    }
};

Python

# from typing import List

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        graph = [[] for _ in range(len(row) // 2)]
        for i in range(0, len(row), 2):
            graph[row[i] // 2].append(row[i + 1] // 2)
            graph[row[i + 1] // 2].append(row[i] // 2)
        visited = [False] * (len(row) // 2)
        ans = 0
        for i in range(len(row) // 2):
            if visited[i]:
                continue
            q = []
            q.append(i)
            visited[i] = True
            thisCnt = 0
            while q:
                thisCnt += 1
                thisPeople = q.pop()
                for nextPeople in graph[thisPeople]:
                    if not visited[nextPeople]:
                        visited[nextPeople] = True
                        q.append(nextPeople)
            ans += thisCnt - 1
        return ans

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/134355602