本文主要是介绍【教3妹学编程-算法题】765. 情侣牵手，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
3妹：2哥2哥，你看到新闻了吗？襄阳健桥医院院长 公然“贩卖出生证明”， 真是太胆大包天了吧。
2哥 : 我也看到新闻了，7人被采取刑事强制措施。 就应该好好查查他们， 一查到底！
3妹：真的是太可气了， 白衣天使，本应该治病救人，没想到竟然能干出这种事情。
2哥 :哎，真相会迟到，但是不会缺席。 幸亏好很多像上官大人这样的打拐志愿者，帮助我们揭开面纱，还原事情的真相，他们是伟大的。
3妹：我一直觉得医生是个伟大的职业，小时候的愿望还是当一名医生， 结果上大学没有报考上医学院， 误打误撞进了计算机。 没想到医院也有这么黑暗的角落。
2哥：说到计算机，岔开个话题， 3妹，今天是不是还没刷题呢？我这里有个题很有意思。
题目：
n 对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手。
人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n-2, 2n-1)。
返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起。 每次交换可选择任意两人，让他们站起来交换座位。
示例 1:
输入: row = [0,2,1,3]
输出: 1
解释: 只需要交换row[1]和row[2]的位置即可。
示例 2:
输入: row = [3,2,0,1]
输出: 0
解释: 无需交换座位，所有的情侣都已经可以手牵手了。
提示:
2n == row.length
2 <= n <= 30
n 是偶数
0 <= row[i] < 2n
row 中所有元素均无重复
思路：
并查集
「首尾相连」这件事情可以使用 并查集 表示，将输入数组相邻位置的两个 编号 在并查集中进行合并。编写代码基于了下面的事实：
如果一对情侣恰好坐在了一起，并且坐在了成组的座位上，其中一个下标一定是偶数，另一个一定是奇数，并且「偶数的值 + 1 = 奇数的值」。例如编号数对 [2, 3]、[9, 8]，这些数对的特点是除以 2（下取整）得到的数相等。
详见代码：
java代码：
public class Solution {public int minSwapsCouples(int[] row) {int len = row.length;int N = len / 2;UnionFind unionFind = new UnionFind(N);for (int i = 0; i < len; i += 2) {unionFind.union(row[i] / 2, row[i + 1] / 2);}return N - unionFind.getCount();}private class UnionFind {private int[] parent;private int count;public int getCount() {return count;}public UnionFind(int n) {this.count = n;this.parent = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;}}public int find(int x) {while (x != parent[x]) {parent[x] = parent[parent[x]];x = parent[x];}return x;}public void union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX == rootY) {return;}parent[rootX] = rootY;count--;}}
}这篇关于【教3妹学编程-算法题】765. 情侣牵手的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
