## 题目描述：

LeetCode 765. Couples Holding Hands

N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

The people and seats are represented by an integer from `0` to `2N-1`, the couples are numbered in order, the first couple being `(0, 1)`, the second couple being `(2, 3)`, and so on with the last couple being `(2N-2, 2N-1)`.

The couples' initial seating is given by `row[i]` being the value of the person who is initially sitting in the i-th seat.

Example 1:

```Input: row = [0, 2, 1, 3]
Output: 1
Explanation: We only need to swap the second (row) and third (row) person.
```

Example 2:

```Input: row = [3, 2, 0, 1]
Output: 0
Explanation: All couples are already seated side by side.
```

Note:

1. `len(row)` is even and in the range of `[4, 60]`.
2. `row` is guaranteed to be a permutation of `0...len(row)-1`.

N对情侣手牵手坐在2N个座位上。

## 解题思路：

```假设第I对情侣编号为sm, bg（sm < bg）

```假设初始3对情侣配对为 [[1, 2], [3, 4], [5, 0]]

[[3, 4], [5, 2]] 可以标准化为 [[0, 3], [1, 2]]

## Python代码：

``````class Solution(object):
def normalize(self, row):
crow = []
for x in range(len(row)):
sm, bg = row[x], row[x]
if sm > bg: sm, bg = bg, sm
if bg % 2 and sm + 1 == bg: continue
crow.append((sm, bg))
shift = {v : i for i, v in enumerate(sorted(reduce(operator.add, crow, ())))}
crow = sorted([shift[sm], shift[bg]] for sm, bg in crow)
return crow

def solve(self, row):
row = self.normalize(row)
if not row: return 0
locs = {}
for idx, (sm, bg) in enumerate(row):
locs[sm], locs[bg] = idx * 2, idx * 2 + 1
row[locs / 2][locs % 2] = row
return self.solve(row[1:]) + 1

def minSwapsCouples(self, row):
"""
:type row: List[int]
:rtype: int
"""
return self.solve([[row[x], row[x + 1]] for x in range(0, len(row), 2)])
``````

Pingbacks已关闭。