C++ 中对数组进行排序所需的最少交换次数
c++server side programmingprogramming
问题描述
给定一个包含 N 个不同元素的数组，求对其进行排序所需的最少交换次数
示例
如果数组元素为 {4, 2, 1, 3}，则需要交换 2 次
- 将 arr[0] 与 arr[2] 交换
- 将 arr[2] 与 arr[3] 交换
算法
1. 使用 C++ 创建一个包含元素对的向量，第一个元素作为数组值，第二个元素作为数组索引。 2. 根据元素对的第一个元素对向量进行排序。 3. 遍历向量并检查与值映射的索引是否正确，如果不正确，则继续交换，直到元素放置正确并继续计算交换次数。
示例
#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(int *arr, int n) {
vector<pair<int, int>> vec(n);
for (int i = 0; i < n; ++i) {
vec[i].first = arr[i];
vec[i].second = i;
}
sort(vec.begin(), vec.end());
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (vec[i].second == i) {
continue;
}
swap(vec[i].first,vec[vec[i].second].first);
swap(vec[i].second,vec[vec[i].second].second);
if (i != vec[i].second) {
--i;
}
++cnt;
}
return cnt;
}
int main() {
int arr[] = {4, 2, 1, 3};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum swaps = " << getMinSwaps(arr, n) <<
endl;
return 0;
}
编译并执行上述程序，将生成以下输出
输出
Minimum swaps = 2
