# \[765]\[困难]\[并查集]\[贪心] 情侣牵手

## 题目描述

[765. 情侣牵手](https://leetcode-cn.com/problems/couples-holding-hands/)

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 的一个全排列。

## 解题思路

### 贪心 + 哈希

每两个位置一组，如果互相不是情侣，把第二个位置的人和第一个位置的人的情侣交换位置. 使用哈希表存储每个人的位置, 用空间换时间.

```python
class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        length = len(row)
        n = length // 2

        mapping = {num: i for i, num in enumerate(row)}

        count = 0
        for i in range(n):
            left, right = i * 2, i * 2 + 1
            lnum, rnum = row[left], row[right]
            other = lnum ^ 1

            if rnum != other:
                count += 1
                other_index = mapping[other]
                row[right], row[other_index] = row[other_index], row[right]
                mapping[rnum] = other_index

        return count
```

### 并查集

[并查集-Union Find](https://leetcode-cn.com/problems/couples-holding-hands/solution/bing-cha-ji-union-find-by-shty/)

```python
class Union:
    def __init__(self, n):
        self.roots = list(range(n))

    def find(self, i):
        if self.roots[i] == i:
            return i
        self.roots[i] = self.find(self.roots[i])
        return self.roots[i]

    def union(self, a, b):
        self.roots[self.find(a)] = self.find(b)

    def connected(self, a, b):
        return self.find(a) == self.find(b)

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        n = len(row)
        union = Union(n // 2)

        for i in range(n // 2):
            left, right = i * 2, i * 2 + 1
            lidx, ridx = row[left] // 2, row[right] // 2
            if lidx != ridx:
                union.union(lidx, ridx)

        count, seen = 0, set()
        for i in range(n // 2):
            index = union.find(i)
            if index not in seen:
                seen.add(index)
                count += 1

        return n // 2 - count
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/tan-xin/765-qing-lv-qian-shou.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.