765.情侣牵手

链接：765.情侣牵手
难度：Hard
标签：贪心、深度优先搜索、广度优先搜索、并查集、图
简介：N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。

题解 1 - typescript

• 编辑时间：2021-02-14
• 执行用时：84ms
• 内存消耗：40.2MB
• 编程语言：typescript
• 解法介绍：储存所有值进行交换。

function minSwapsCouples(row: number[]): number {
  const map: Record<number, number> = {};
  row.forEach((num, i) => (map[num] = i));
  const swap = (num1: number, num2: number) => {
    [row[map[num1]], row[map[num2]]] = [row[map[num2]], row[map[num1]]];
    [map[num1], map[num2]] = [map[num2], map[num1]];
  };
  let ans = 0;
  for (let i = 0, l = row.length - 1; i < l - 1; i += 2) {
    const num = row[i];
    const nextNum = row[i + 1];
    const needNum = num & 1 ? num - 1 : num + 1;
    if (nextNum !== needNum) {
      ans++;
      swap(needNum, nextNum);
    }
  }
  return ans;
}

题解 2 - python

• 编辑时间：2023-11-11
• 执行用时：48ms
• 内存消耗：15.68MB
• 编程语言：python
• 解法介绍：贪心的每次没有匹配上去重置。

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        n = len(row)
        map = {row[i]: i for i in range(n)}
        ans = 0
        for i in range(0, n, 2):
            if row[i] ^ 1 != row[i + 1]:
                map[row[i + 1]] = map[row[i] ^ 1]
                row[map[row[i] ^ 1]], row[i + 1] = row[i + 1], row[map[row[i] ^ 1]]
                ans += 1
        return ans