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

在本教程中,我们将编写一个程序,该程序在最多k个交换之后找到最大的排列。

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

  • 初始化数组。

  • 初始化数组以存储大小为n + 1的索引。

  • 遍历数组并将每个元素的索引存储在position数组中。

  • 编写一个循环,直到n和k大于0为止。

    • 将n-i元素的位置存储在临时变量中。

    • 用position [n-i]更新当前元素arr [i]的位置。

    • 用当前索引i更新位置position [n-i]。

    • 将当前元素arr[i]与arr [temp] 递减k。

  • 打印数组元素。

示例

让我们看一下代码。

#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

以上是 在C ++中最多进行k次交换后的最大排列 的全部内容, 来源链接: utcz.com/z/338861.html

回到顶部