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

题目描述

765. 情侣牵手

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

解题思路

贪心 + 哈希

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

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

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