数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究C++ 中对数组进行排序所需的最少交换次数
问题陈述
给定一个 N 个不同元素的数组，查找对数组进行排序所需的最小交换次数
示例
如果数组为 {4, 2, 1, 3} 则需要 2 次交换
- 将 arr[0] 与 arr[2] 交换
- 将 arr[2] 与 arr[3} 交换
算法
1. Create a vector of pair in C++ with first element as array alues and second element as array indices. 2. Sort the vector of pair according to the first element of the pairs. 3. Traverse the vector and check if the index mapped with the value is correct or not, if not then keep swapping until the element is placed correctly and keep counting the number of swaps.
示例
#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
更新时间：2019 年 12 月 23 日
486 次浏览
Anuncios