题目
N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。
人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)。
这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。
代码
public class DayCode { public static void main(String[] args) { int[] nums = new int[]{0, 2, 1, 3}; Integer ans = new DayCode().minSwapsCouples(nums); System.out.println("ans is " + ans); }
/** * https://leetcode-cn.com/problems/couples-holding-hands/ * @param row * @return */ 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--; } }}
复制代码
总结
评论