C++で配列をM回連結したときのK番目に小さい要素を求める方法

問題の概要

配列Aと、2つの整数K・Mが与えられたとします。このとき、配列Aを自分自身にM回連結した後の配列から、K番目に小さい要素を求める必要があります。

例として、配列が A = [3, 1, 2]、K = 4、M = 3 の場合を考えてみましょう。配列Aを3回連結すると [3, 1, 2, 3, 1, 2, 3, 1, 2] となり、この中で4番目に小さい要素は「2」です。

解法のアプローチ

一見すると、実際に配列をM回連結して巨大な配列を作り、そこからK番目に小さい要素を探す必要があるように思えます。しかし、それではメモリ使用量や計算時間が無駄にかかってしまいます。

ここで重要なポイントは、同じ配列を繰り返し連結しても、各要素の出現頻度は均等にM倍になるという点です。したがって、元の配列Aをソートしておけば、連結後の配列におけるK番目に小さい要素は、ソート済み配列のインデックス ((K - 1) / M) の位置にある値と一致します。

つまり、解法の手順は以下の通りです。

1. 配列Aをソートする
2. インデックス (K - 1) / M の位置にある要素を返す

これにより、実際に連結を行うことなく、O(N log N) の計算量で効率的に答えを求められます。

実装例(C++)

#include<iostream>
#include<algorithm>
using namespace std;

int findKSmallestNumber(int A[], int N, int M, int K) {
    sort(A, A + N);
    return (A[((K - 1) / M)]);
}

int main() {
    int A[] = { 3, 1, 2 };
    int M = 3, K = 4;
    int N = sizeof(A) / sizeof(A[0]);
    cout << K << "番目に小さい数(連結" << M << "回): "
         << findKSmallestNumber(A, N, M, K);
}

出力結果

4番目に小さい数(連結3回): 2

処理の流れの解説

上記のコードでは、まず sort() 関数を使って配列Aを昇順に並べ替えています。ソート後の配列は [1, 2, 3] となります。

K = 4、M = 3 の場合、(K - 1) / M = 3 / 3 = 1 となるため、インデックス1の位置にある要素、すなわち「2」が返されます。これは、連結後の配列 [3, 1, 2, 3, 1, 2, 3, 1, 2] をソートした [1, 1, 1, 2, 2, 2, 3, 3, 3] の4番目の要素と一致しています。

まとめ

配列をM回連結した場合のK番目に小さい要素を求める問題は、実際に連結を行わずとも、元の配列をソートしてインデックス (K - 1) / M の要素を参照するだけで解決できます。このテクニックを使えば、大きなメモリを消費することなく、シンプルかつ高速に目的の値を取得できます。