C++でk以下のすべての要素をまとめるために必要な最小スワップ

問題の説明

n個の正の整数と数kの配列が与えられます。 k以下のすべての数をまとめるのに必要なスワップの最小数を見つけます。

例

入力配列が=1、5、4、7、2、10}でk =6の場合、1つのスワップが必要です。つまり、要素7を2とスワップします。

アルゴリズム

• 「k」以下のすべての要素をカウントします。カウントが「cnt」であるとしましょう
• 長さ「cnt」のウィンドウに2つのポインター手法を使用して、この範囲内の「k」より大きい要素の数を毎回追跡します。合計数が「outOfRange」であるとしましょう。
• 長さが「cnt」のウィンドウごとに手順2を繰り返し、その中の「outOfRange」のカウントを最小にします。これが最終的な答えになります。

例

#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(int *arr, int n, int k) {
   int cnt = 0;
   for (int i = 0; i < n; ++i) {
      if (arr[i] <= k) {
         ++cnt;
      }
   }
   int outOfRange = 0;
   for (int i = 0; i < cnt; ++i) {
      if (arr[i] > k) {
         ++outOfRange;
      }
   }
   int result = outOfRange;
   for (int i = 0, j = cnt; j < n; ++i, ++j) {
      if (arr[i] > k) {
         --outOfRange;
      }
      if (arr[j] > k) {
         ++outOfRange;
      }
      result = min(result, outOfRange);
   }
   return result;
}
int main() {
   int arr[] = {1, 5, 4, 7, 2, 10};
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 6;
   cout << "Minimum swaps = " << getMinSwaps(arr, n, k) <<
   endl;
   return 0;
}

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

出力

Minimum swaps = 1