leecode 765 情侣牵手问题，并查集+问题转换能力

本文主要是介绍leecode 765 情侣牵手问题，并查集+问题转换能力，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

分析：假设有 N对情侣，假设有 K 个集合（存在情侣的集合），（偶数，偶数+1）为一个元素最少的集合这种情况符合题意不需要交换。假设每个集合里面有 m1，m2, m3.......mk个元素，需要进行m1-1，m2-1, m3-1.......mk-1次交换，求和得到本题答案为N - K

class UnionSet:
    def __init__(self, n):
        self.father = list(range(n))
    def find(self, ind): #找寻元素的根节点
        if self.father[ind] == ind:
            return ind
        self.father[ind] = self.find(self.father[ind]) 
        return self.father[ind]
    def union(self, x, y): #将y并入x类
        root_x = self.find(x) #x位置元素，根节点为root_x编号元素
        root_y = self.find(y) #y位置元素，根节点为root_y编号元素
        if root_x != root_y:              
            self.father[root_y] = root_x #把root_y编号元素的父节点，替换为root_x
        return
    def isConnection(self, x, y):
        return self.find(x) == self.find(y)

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        n = len(row) // 2
        us = UnionSet(n)
        for i in range(0, len(row) , 2):
            left = row[i] // 2
            right = row[i+1] // 2

            if left != right:
                us.union(left, right)

        set_count = 0
        for i in range(n):
            if us.find(i) == i:
                set_count += 1

        return n - set_count

这篇关于leecode 765 情侣牵手问题，并查集+问题转换能力的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！