福建建设职业管理中心网站,应用制作下载,wordpress 升级提示,泰州网站建设 思创首先不考虑已经正确坐在一起的组合在没有坐在一起的组合中#xff0c;只有当两对情侣互相配对时只需要一次交换操作就可以使得两对情侣完成匹配#xff0c;其余情况交换数等于情侣对数可以把所有情侣看成一个大集合#xff0c;这个大集合是可以拆成若干小集合的#xff0c;…
首先不考虑已经正确坐在一起的组合在没有坐在一起的组合中只有当两对情侣互相配对时只需要一次交换操作就可以使得两对情侣完成匹配其余情况交换数等于情侣对数可以把所有情侣看成一个大集合这个大集合是可以拆成若干小集合的比如对于排列0471652983显然前六个047165之间的交换仅发生在前六个之中与后四个无关按照这样的规则我们可以把整个集合分割成不存在正确匹配内部可完成交换不可再分割的若干小集合现在问题转化为求解 3 中描述的小集合的最少交换次数对于这样的集合只有在最后一次交换的时候才会发生在第二步中描述的第一种情况因为如果在最后一次交换前发生了这种情况假设是第 k 次交换是两两匹配的那么在第 k 次交换前的所有情侣的组合就可以构成一个更小的组合不满足我们一开始的假设总结如果 ij 靠在一起那么那他们必定是同一个小集合的通过将 i 节点与 j 节点连接的方式来表示它们属于一个集合最终我们会的到一张非连通图答案就是每一个连通分量的大小 -1 的和
class Solution:def minSwapsCouples(self, row: List[int]) - int:near defaultdict(list)vis set()for i in range(0, len(row), 2):if row[i] // 2 row[i 1] // 2:vis.add(row[i] // 2)continuenear[row[i] // 2].append(row[i 1] // 2)near[row[i 1] // 2].append(row[i] // 2)ans 0for i in range(len(row) // 2):if i in vis:continuet [i]while len(t) 0:for _ in range(len(t)):k t.pop()if k in vis:continuevis.add(k)t.extend(near[k])ans 1ans - 1return ans
