グループごとに任意の数の結果を含む未分類の結果リストのk番目のグループを取得する

Question

わかりましたので、未知のデータ型の未分類要素がたくさんあります（すべての要素は同じ型ですが、数値、文字列、または<と>演算子をオーバーロードする任意の種類のオブジェクトである可能性があります。これらのオブジェクトについて私が作ることができる唯一の仮定は、それらの2つが同じではなく、それらを比較することです（A < B）

私はこのソートされていない配列を受け取ります（std :: vectorと入力しますが、正直なところアルゴリズムの問​​題ですので特に言語はありません）。期待される）、「グループ」（groupSize）当たりの多数のオブジェクト、およびグループ番号th送信者のwant（groupNumber）に送信します。

私は、groupSize要素を含む配列を返すか、要求されたグループが最後のものである場合はそれより少ない数を返します。 （例：あなたは四群を求める場合は5のGROUPSIZEと17回の結果は2つのみを返すでしょう、それはゼロインデックス付きの配列ですので、また、第4グループは、グループ番号3である。）

例：

受信アレイ：{1、5、8、2、19、-1、6、6.5、-14、20}

受信のpageSize：3

受信ページ番号：2

アレイであった場合ソートされると、次のようになります。{-14、-1,1,2,5,6,6.5,8,19,20}

それはサイズ3のグループに分割された場合：{{-14、-1、1}、{2、5、6}、{6.5、8、19}、{20}}

I （0インデックス配列のpageNumber 2）を返す必要があります。{6.5,8,19}

最大の問題は、高速である必要があるという事実です。私はO（n log n）よりも速くなければならないので配列をソートできません。

私はいくつかの方法を試みましたが、O（n log n）の下では決してできません。

私は、他のすべてのグループを満たしていないソリューションを探して、上記の例に示したかなりの部分をスキップして、要求されたグループのみを作成して戻すことを知っていますしかし、私はそれを行う方法を理解することはできません。

Answer 1

標準のC++ std::nth_element関数を使用して、グループ内の最小の要素sの値を線形時間で見つけることができます（ソートされた配列のインデックスがわかっているため）。グループ内で最大の要素Sを同じ方法で見つけることができます。その後、xのすべての要素を見つけてs <= x <= Sというリニアパスが必要です。総時間複雑度はO(n)です。

注：この回答はC++固有のものではありません。線形時間でのk次統計の実装が必要です。