3妹:2哥2哥,你看到新闻了吗?襄阳健桥医院院长 公然“贩卖出生证明”, 真是太胆大包天了吧。
2哥 : 我也看到新闻了,7人被采取刑事强制措施。 就应该好好查查他们, 一查到底!
3妹:真的是太可气了, 白衣天使,本应该治病救人,没想到竟然能干出这种事情。
2哥 :哎,真相会迟到,但是不会缺席。 幸亏好很多像上官大人这样的打拐志愿者,帮助我们揭开面纱,还原事情的真相,他们是伟大的。
3妹:我一直觉得医生是个伟大的职业,小时候的愿望还是当一名医生, 结果上大学没有报考上医学院, 误打误撞进了计算机。 没想到医院也有这么黑暗的角落。
2哥:说到计算机,岔开个话题, 3妹,今天是不是还没刷题呢?我这里有个题很有意思。
1题目:
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 中所有元素均无重复
2思路:
并查集
「首尾相连」这件事情可以使用 并查集 表示,将输入数组相邻位置的两个 编号 在并查集中进行合并。编写代码基于了下面的事实:
如果一对情侣恰好坐在了一起,并且坐在了成组的座位上,其中一个下标一定是偶数,另一个一定是奇数,并且「偶数的值 + 1 = 奇数的值」。例如编号数对 [2, 3]、[9, 8],这些数对的特点是除以 2(下取整)得到的数相等。
详见代码:
3java代码:
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--;
}
}
}
标签:parent,int,情侣,妹学,牵手,座位,765,public,row
From: https://blog.51cto.com/u_6813689/8325068