【C++】k以下の要素をすべてまとめるのに必要な最小スワップ回数を求める方法

問題の概要

正の整数からなる長さ n の配列と、ある数値 k が与えられます。「k 以下の数値」をすべて配列内で隣り合うように集めるために、最低何回のスワップ(要素の入れ替え)が必要かを求めてください。

入力例

たとえば、入力配列が {1, 5, 4, 7, 2, 10}、k = 6 の場合を考えてみましょう。このとき必要なスワップは 1 回だけです。具体的には、7 と 2 を入れ替えることで、6 以下の要素(1, 5, 4, 2)がすべて連続して並ぶようになります。

解法のアプローチ

この問題は、スライディングウィンドウ(二ポインタ)のテクニックを使うことで O(n) で効率よく解くことができます。手順は以下の通りです。

• まず、配列内にある「k 以下の要素」の総数を数えます。この個数を cnt とします。
• 次に、長さ cnt のウィンドウを配列上で順にスライドさせながら、各ウィンドウ内に含まれる「k より大きい要素」の個数を数えます。この個数を outOfRange とします。
• すべてのウィンドウ位置について同様の処理を繰り返し、outOfRange の最小値を求めます。この最小値が最終的な答えとなります。

なぜこれで正しく求まるのかというと、k 以下の要素が最終的に占める領域の長さは必ず cnt になるため、その領域内に「k より大きい要素」がいくつ残っているかが、そのまま必要なスワップ回数に対応するからです。領域の開始位置を全パターン試し、その中で最も入れ替えが少ないものを採用すればよいわけです。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;

int getMinSwaps(int *arr, int n, int k) {
    // k以下の要素の個数をカウント
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i] <= k) {
            ++cnt;
        }
    }

    // 最初のウィンドウ(長さcnt)内の「kより大きい要素」を数える
    int outOfRange = 0;
    for (int i = 0; i < cnt; ++i) {
        if (arr[i] > k) {
            ++outOfRange;
        }
    }

    // ウィンドウを1つずつ右へスライドさせながら最小値を更新
    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;
}

コードのポイント

• 最初に k 以下の要素数 cnt を求め、これが「まとめるべき領域のサイズ」となります。
• 最初のウィンドウに対して outOfRange を計算した後、ウィンドウを 1 つ右にずらすたびに、左端から出ていく要素と右端に入ってくる要素だけを差分更新しています。これにより、毎回ウィンドウ全体を再計算せずに済みます。

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Minimum swaps = 1

このように、配列 {1, 5, 4, 7, 2, 10} に対して k = 6 の場合、必要なスワップ回数は 1 回であることが確認できます。