資料結構
網路
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