数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++程序：查找将所有袜子对排列在一起所需的最小交换次数
假设我们有一个名为row的数字列表，它表示一行中排列的袜子。它们没有排序，但我们希望重新排列它们，以便每对袜子并排放置，例如 (0, 1)、(2, 3)、(4, 5) 等。我们需要找到重新排列它们所需的最小交换次数。
因此，如果输入类似于 row = [0, 5, 6, 2, 1, 3, 7, 4]，则输出将为 2，因为行顺序为
[0, 5, 6, 2, 1, 3, 7, 4]
[0, 1, 6, 2, 5, 3, 7, 4]
[0, 1, 3, 2, 5, 6, 7, 4]
[0, 1, 3, 2, 5, 4, 7, 6]
为了解决这个问题，我们将遵循以下步骤：
定义一个数组 p 和另一个数组 sz
定义一个函数 find()，它将接收 u，
返回（如果 p[u] 与 u 相同，则返回 u，否则返回 find(p[u]) 并将 p[u] := find(p[u])）
定义一个函数 join()，它将接收 u、v，
pu := find((u), pv := find(v)
如果 pu 与 pv 相同，则：
返回
如果 sz[pu] >= sz[pv]，则：
p[pv] := pu
sz[pu] := sz[pu] + sz[pv]
否则
p[pu] := pv
sz[pv] := sz[pv] + sz[pu]
从主方法执行以下操作：
n := arr 的大小
p := 一个大小为 n 的数组
初始化 i := 0，当 i < n 时，更新（i 增加 1），执行：
p[i] := i
sz := 一个大小为 n 的数组，并填充为 1
初始化 i := 0，当 i < n 时，更新（i 增加 1），执行：
u := arr[i/2] / 2
v := arr[(i/2) OR 1] / 2
join(u, v)
ans := 0
初始化 i := 0，当 i < n 时，更新（i 增加 1），执行：
如果 find(i) 与 i 相同，则：
ans := ans + sz[i] − 1
返回 ans
让我们查看以下实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
vector<int> p, sz;
int find(int u) {
return p[u] == u ? u : p[u] = find(p[u]);
}
void join(int u, int v) {
int pu = find(u), pv = find(v);
if (pu == pv)
return;
if (sz[pu] >= sz[pv]) {
p[pv] = pu;
sz[pu] += sz[pv];
}else {
p[pu] = pv;
sz[pv] += sz[pu];
}
}
int solve(vector<int>& arr) {
int n = arr.size() / 2;
p = vector<int>(n);
for (int i = 0; i < n; ++i)
p[i] = i;
sz = vector<int>(n, 1);
for (int i = 0; i < n; ++i) {
int u = arr[i << 1] / 2;
int v = arr[i << 1 | 1] / 2;
join(u, v);
}
int ans = 0;
for (int i = 0; i < n; ++i)
if (find(i) == i)
ans += sz[i] − 1;
return ans;
}
int main(){
vector<int> v = {0, 5, 6, 2, 1, 3, 7, 4};
cout << solve(v);
}输入
{2, 4, 6, 3}输出
23
139 次浏览
