C++で最大k回のスワップ後の最大の順列

このチュートリアルでは、最大k回のスワップ後に最大の順列を見つけるプログラムを作成します。

問題を解決するための手順を見てみましょう。

• アレイを初期化します。
• 配列を初期化して、サイズn+1のインデックスを格納します。
• 配列を反復処理し、各要素のインデックスを位置配列に格納します。
• nとkが0より大きくなるまで繰り返すループを記述します。
  • n-i要素の位置を一時変数に格納します。
  • 現在の要素arr[i]の位置をposition[n-i]で更新します。
  • 現在のインデックスiで位置位置[n-i]を更新します。
  • 現在の要素arr[i]をarr[temp.Decrementk。
  と交換します。
• 配列要素を印刷します。

例

コードを見てみましょう。

#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

結論

チュートリアルに質問がある場合は、コメントセクションにそのことを記載してください。