【C++】n個の数値からなる集合Sの中で、中央値に最も近いk個の数を見つける方法

本記事では、n個の数値からなる集合Sが与えられたとき、その中央値（メジアン）に最も近いk個の数を求めるC++プログラムを紹介します。

この問題は、まずクイックソートでデータを並べ替え、その後中央値を基準として左右にポインタを広げながら近い順に要素を選んでいくというアプローチで解くことができます。

アルゴリズムの概要

処理は大きく分けて「パーティション（分割）」「クイックソート」「中央値からの探索」の3段階で構成されます。

1. partition関数：配列の分割

配列a[]の末尾の値（high）をピボットとして扱い、それより小さい要素を左側に集めることで配列を分割します。

Begin
    function partition()：high位置の値をピボットとして配列を分割する
    引数：
        a[] = 配列
        l = low（下限インデックス）
        h = high（上限インデックス）
    関数本体：
        pivot、in、i を宣言
        in = l で初期化
        pivot = h を設定
        i = l から h-1 まで繰り返し：
            if (a[i] < a[pivot])
                a[i] と a[in] を入れ替える
                in をインクリメント
        a[pivot] と a[in] を入れ替える
        in を返す
End

2. QuickSort関数：クイックソートによる並べ替え

上記のpartition関数を利用し、再帰的にデータ要素をソートします。

Begin
    function QuickSort()：クイックソートでデータを整列する
    引数：
        a[] = 配列
        l = low（下限インデックス）
        h = high（上限インデックス）
    関数本体：
        pindex を宣言
        if (l < h)
            index = Partition(a, l, h)
            QuickSort(a, l, pindex-1)
            QuickSort(a, pindex+1, h)
        return 0
End

3. main関数：中央値の算出と近傍要素の出力

データ要素数が奇数の場合は中央の要素を中央値とし、偶数の場合は中央の2つの値の平均を中央値とします。その後、k回ループして中央値により近い要素を順に出力します。

Begin
    function main()
    データ要素数が奇数の場合：
        中央のインデックスを low、その隣のインデックスを high とし、中央値を計算
        k回ループし、中央値により近い要素を出力
    偶数の場合：
        中央値は中央2つの値の平均となる
        k回ループし、中央値により近い要素を出力
End

C++サンプルコード

以下が実際の実装例です。swap関数、Partition関数、QuickSort関数、main関数で構成されています。

#include<iostream>
using namespace std;
void swap(int *x, int *y) { //2つの値を入れ替える 
    int tmp;
    tmp = *x;
    *x = *y;
    *y = tmp;
}
int Partition(int a[], int l, int h) {
    int pivot, in, i;
    in = l;
    pivot = h;
    for(i=l; i < h; i++) {
        if(a[i] < a[pivot]) {
            swap(&a[i], &a[in]);
            in++;
        }
    }
    swap(&a[pivot], &a[in]);
    return in;
}
int QuickSort(int a[], int l, int h) {
    int pindex;
    if(l < h) {
        pindex = Partition(a, l, h);
        QuickSort(a, l, pindex-1);
        QuickSort(a, pindex+1, h);
    }
    return 0;
}
int main() {
    int n, i, h, l, k;
    double d1,d2, median;
    cout<<"Enter the number of element in dataset: ";
    cin>>n;
    int a[n];
    for(i = 0; i < n; i++) {
        cout<<"\nEnter "<<i+1<<" element: ";
        cin>>a[i];
    }
    cout<<"\nEnter the number of element nearest to the median required: ";
    cin>>k;
    QuickSort(a, 0, n-1);
    cout<<"The K element nearest to the median are: ";
    if(n%2 == 1) {
        median = a[n/2];
        h = n/2+1;
        l= n/2;
        while(k > 0) {
            if((median-a[l] <= a[h]-median) && l >= 0) {
                cout<<" "<<a[l];
                l--;
                k--;
            } else if((median-a[l] > a[h]-median) && h <= n-1) {
                cout<<" "<<a[h];
                h++;
                k--;
            }
        }
    } else {
        d1 = a[n/2];
        d2 = a[n/2-1];
        median = (d1+d2)/2;
        h = n/2;
        l = n/2-1;
        while(k > 0) {
            d1 = a[l];
            d2 = a[h];
            if((median-d2 <= d1-median) && l >= 0) {
                cout<<" "<<a[l];
                l--;
                k--;
            } else if((median-d2 > d1-median) && h <= n-1) {
                cout<<" "<<a[h];
                h++;
                k--;
            }
        }
    }
    return 0;
}

実行結果の例

7個の要素（1〜7）を持つデータセットに対して、中央値に最も近い2つの要素を求めた場合の実行例です。中央値は4となり、その両隣にある「4」と「3」が出力されます。

Enter the number of element in dataset: 7
Enter 1 element: 7
Enter 2 element: 6
Enter 3 element: 5
Enter 4 element: 4
Enter 5 element: 3
Enter 6 element: 2
Enter 7 element: 1
Enter the number of element nearest to the median required: 2
The K element nearest to the median are: 4 3

ポイントのまとめ

• まずクイックソートでデータを昇順に並べ替えることで、中央値の位置を特定しやすくなります。
• 要素数が奇数の場合は中央の1つの値、偶数の場合は中央2つの平均が中央値になります。
• 中央値を起点に左右のインデックス（l と h）を比較しながら広げていくことで、距離の近い順にk個の要素を効率的に取り出せます。