C++中最多k次交换后的最大排列

在本教程中，我们将编写一个程序，查找最多进行k次交换后的最大排列。

让我们看看解决这个问题的步骤。

  • 初始化数组。
  • 初始化一个大小为n+1的数组来存储索引。
  • 遍历数组，并将每个元素的索引存储在position数组中。
  • 编写一个循环，直到n次迭代完成且k大于0。
    • 将n - i元素的位置存储在一个临时变量temp中。
    • 用position[n - i]更新当前元素arr[i]的位置。
    • 用当前索引i更新position[n - i]。
    • 将当前元素arr[i]与arr[temp]交换。k减1。
  • 打印数组元素。

示例

让我们看看代码。

 在线演示

#include <bits/stdc++.h>
using namespace std;
void getLargestPermutation(int arr[], int n, int k) {
   int position[n + 1];
   for (int i = 0; i < n; ++i) {
      position[arr[i]] = i;
   }
   for (int i = 0; i < n && k; ++i) {
      if (arr[i] == n - i) {
         continue;
      }
      int temp = position[n - i];
      position[arr[i]] = position[n - i];
      position[n - i] = i;
      swap(arr[temp], arr[i]);
      --k;
   }
}
int main() {
   int arr[] = { 5, 3, 2, 6, 7, 1, 4 };
   int n = 7, k = 3;
   getLargestPermutation(arr, n, k);
   for (int i = 0; i < n; ++i) {
      cout << arr[i];
   }
   cout << endl;
   return 0;
}

输出

如果您运行上述代码，则会得到以下结果。

7653214

结论

如果您在本教程中遇到任何疑问，请在评论区提出。

更新于：2021年4月9日

556 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告