資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
