class Solution {
public:
int minSwapsCouples(vector<int>& row) {
}
};
765. 情侣牵手
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.length2 <= n <= 30n 是偶数0 <= row[i] < 2nrow 中所有元素均无重复原站题解
cpp 解法, 执行用时: 4 ms, 内存消耗: 7.9 MB, 提交时间: 2023-11-11 00:23:28
class Solution {
public:
int minSwapsCouples(vector<int>& row) {
int n = row.size();
int tot = n / 2;
vector<vector<int>> graph(tot);
for (int i = 0; i < n; i += 2) {
int l = row[i] / 2;
int r = row[i + 1] / 2;
if (l != r) {
graph[l].push_back(r);
graph[r].push_back(l);
}
}
vector<int> visited(tot, 0);
int ret = 0;
for (int i = 0; i < tot; i++) {
if (visited[i] == 0) {
queue<int> q;
visited[i] = 1;
q.push(i);
int cnt = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
cnt += 1;
for (int y: graph[x]) {
if (visited[y] == 0) {
visited[y] = 1;
q.push(y);
}
}
}
ret += cnt - 1;
}
}
return ret;
}
};
cpp 解法, 执行用时: 4 ms, 内存消耗: 7.7 MB, 提交时间: 2023-11-11 00:23:17
class Solution {
public:
int getf(vector<int>& f, int x) {
if (f[x] == x) {
return x;
}
int newf = getf(f, f[x]);
f[x] = newf;
return newf;
}
void add(vector<int>& f, int x, int y) {
int fx = getf(f, x);
int fy = getf(f, y);
f[fx] = fy;
}
int minSwapsCouples(vector<int>& row) {
int n = row.size();
int tot = n / 2;
vector<int> f(tot, 0);
for (int i = 0; i < tot; i++) {
f[i] = i;
}
for (int i = 0; i < n; i += 2) {
int l = row[i] / 2;
int r = row[i + 1] / 2;
add(f, l, r);
}
unordered_map<int, int> m;
for (int i = 0; i < tot; i++) {
int fx = getf(f, i);
m[fx]++;
}
int ret = 0;
for (const auto& [f, sz]: m) {
ret += sz - 1;
}
return ret;
}
};
python3 解法, 执行用时: 40 ms, 内存消耗: 15 MB, 提交时间: 2023-01-11 10:19:18
# 循环搜索
class Solution():
def minSwapsCouples(self, row: List[int]) -> int:
N = len(row) // 2
#couples[x] = [i, j]:
#x-th couple is at couches i and j
couples = [[] for _ in range(N)]
for i, x in enumerate(row):
couples[x//2].append(i//2)
#adj[x] = [i, j]
#x-th couch connected to couches i, j by couples
adj = [[] for _ in range(N)]
for x, y in couples:
adj[x].append(y)
adj[y].append(x)
#Answer is N minus the number of cycles in "adj"
ans = N
for start in range(N):
if not adj[start]: continue
ans -= 1
x, y = start, adj[start].pop()
while y != start:
adj[y].remove(x)
x, y = y, adj[y].pop()
return ans
python3 解法, 执行用时: 36 ms, 内存消耗: 14.9 MB, 提交时间: 2023-01-11 10:17:28
# 贪心法，
class Solution():
def minSwapsCouples(self, row: List[int]) -> int:
ans = 0
for i in range(0, len(row), 2):
x = row[i]
if row[i+1] == x^1: continue
ans += 1
for j in range(i+1, len(row)):
if row[j] == x^1:
row[i+1], row[j] = row[j], row[i+1]
break
return ans
java 解法, 执行用时: 1 ms, 内存消耗: 39.3 MB, 提交时间: 2023-01-11 10:15:40
class Solution {
public int minSwapsCouples(int[] row) {
int n = row.length;
int tot = n / 2;
List<Integer>[] graph = new List[tot];
for (int i = 0; i < tot; i++) {
graph[i] = new ArrayList<Integer>();
}
for (int i = 0; i < n; i += 2) {
int l = row[i] / 2;
int r = row[i + 1] / 2;
if (l != r) {
graph[l].add(r);
graph[r].add(l);
}
}
boolean[] visited = new boolean[tot];
int ret = 0;
for (int i = 0; i < tot; i++) {
if (!visited[i]) {
Queue<Integer> queue = new LinkedList<Integer>();
visited[i] = true;
queue.offer(i);
int cnt = 0;
while (!queue.isEmpty()) {
int x = queue.poll();
cnt += 1;
for (int y : graph[x]) {
if (!visited[y]) {
visited[y] = true;
queue.offer(y);
}
}
}
ret += cnt - 1;
}
}
return ret;
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-01-11 10:14:58
func minSwapsCouples(row []int) (ans int) {
n := len(row)
graph := make([][]int, n/2)
for i := 0; i < n; i += 2 {
l, r := row[i]/2, row[i+1]/2
if l != r {
graph[l] = append(graph[l], r)
graph[r] = append(graph[r], l)
}
}
vis := make([]bool, n/2)
for i, vs := range vis {
if !vs {
vis[i] = true
cnt := 0
q := []int{i}
for len(q) > 0 {
cnt++
v := q[0]
q = q[1:]
for _, w := range graph[v] {
if !vis[w] {
vis[w] = true
q = append(q, w)
}
}
}
ans += cnt - 1
}
}
return
}
javascript 解法, 执行用时: 60 ms, 内存消耗: 41.3 MB, 提交时间: 2023-01-11 10:14:37
/**
* @param {number[]} row
* @return {number}
*/
var minSwapsCouples = function(row) {
const n = row.length;
const tot = n / 2;
const graph = new Array(tot).fill(0).map(() => []);
for (let i = 0; i < n; i += 2) {
const l = Math.floor(row[i] / 2);
const r = Math.floor(row[i + 1] / 2);
if (l != r) {
graph[l].push(r);
graph[r].push(l);
}
}
const visited = new Array(tot).fill(false);
let ret = 0;
for (let i = 0; i < tot; i++) {
if (!visited[i]) {
const queue = [];
visited[i] = true;
queue.push(i);
let cnt = 0;
while (queue.length) {
const x = queue.shift();
cnt += 1;
for (const y of graph[x]) {
if (!visited[y]) {
visited[y] = true;
queue.push(y);
}
}
}
ret += cnt - 1;
}
}
return ret;
};
javascript 解法, 执行用时: 64 ms, 内存消耗: 41 MB, 提交时间: 2023-01-11 10:13:57
/**
* @param {number[]} row
* @return {number}
*/
var minSwapsCouples = function(row) {
const n = row.length;
const tot = n / 2;
const f = new Array(tot).fill(0).map((element, index) => index);
for (let i = 0; i < n; i += 2) {
const l = Math.floor(row[i] / 2);
const r = Math.floor(row[i + 1] / 2);
add(f, l, r);
}
const map = new Map();
for (let i = 0; i < tot; i++) {
const fx = getf(f, i);
if (map.has(fx)) {
map.set(fx, map.get(fx) + 1);
} else {
map.set(fx, 1)
}
}
let ret = 0;
for (const [f, sz] of map.entries()) {
ret += sz - 1;
}
return ret;
};
const getf = (f, x) => {
if (f[x] === x) {
return x;
}
const newf = getf(f, f[x]);
f[x] = newf;
return newf;
}
const add = (f, x, y) => {
const fx = getf(f, x);
const fy = getf(f, y);
f[fx] = fy;
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-01-11 10:13:28
type unionFind struct {
parent, size []int
setCount int // 当前连通分量数目
}
func newUnionFind(n int) *unionFind {
parent := make([]int, n)
size := make([]int, n)
for i := range parent {
parent[i] = i
size[i] = 1
}
return &unionFind{parent, size, n}
}
func (uf *unionFind) find(x int) int {
if uf.parent[x] != x {
uf.parent[x] = uf.find(uf.parent[x])
}
return uf.parent[x]
}
func (uf *unionFind) union(x, y int) {
fx, fy := uf.find(x), uf.find(y)
if fx == fy {
return
}
if uf.size[fx] < uf.size[fy] {
fx, fy = fy, fx
}
uf.size[fx] += uf.size[fy]
uf.parent[fy] = fx
uf.setCount--
}
func minSwapsCouples(row []int) int {
n := len(row)
uf := newUnionFind(n / 2)
for i := 0; i < n; i += 2 {
uf.union(row[i]/2, row[i+1]/2)
}
return n/2 - uf.setCount
}
java 解法, 执行用时: 1 ms, 内存消耗: 39.2 MB, 提交时间: 2023-01-11 10:13:08
class Solution {
public int minSwapsCouples(int[] row) {
int n = row.length;
int tot = n / 2;
int[] f = new int[tot];
for (int i = 0; i < tot; i++) {
f[i] = i;
}
for (int i = 0; i < n; i += 2) {
int l = row[i] / 2;
int r = row[i + 1] / 2;
add(f, l, r);
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < tot; i++) {
int fx = getf(f, i);
map.put(fx, map.getOrDefault(fx, 0) + 1);
}
int ret = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
ret += entry.getValue() - 1;
}
return ret;
}
public int getf(int[] f, int x) {
if (f[x] == x) {
return x;
}
int newf = getf(f, f[x]);
f[x] = newf;
return newf;
}
public void add(int[] f, int x, int y) {
int fx = getf(f, x);
int fy = getf(f, y);
f[fx] = fy;
}
}
java 解法, 执行用时: 0 ms, 内存消耗: 39.2 MB, 提交时间: 2023-01-11 10:12:36
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--;
}
}
}