在C ++中对数组排序所需的最小交换次数

  • Z时代
  • 2024-01-10
  • 分类：综合

问题陈述

给定一个由N个不同元素组成的数组，请找到对数组进行排序所需的最小交换次数

示例

如果array为{4，2，1，3}，则需要2次交换

  • 将arr [0]与arr [2]交换

  • 用arr [3]交换arr [2]

算法

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

以上是 在C ++中对数组排序所需的最小交换次数 的全部内容， 来源链接： utcz.com/z/351571.html

回到顶部