c++ - C++ リンク リスト (並べ替えなし) で最大 3 つの整数を効率的に取得する

Question

配列の最大 n 個の整数を与える std 関数がいくつかあると聞きましたが、連結リストはどうでしょうか?

解決策は、リンクされたリストを反復処理するための for ループをいくつか用意することだと思いますが、C++ ライブラリにはもっと簡単な解決策があるようです。

ありがとう。

Answer 1

別のデータ構造を使用できない場合は、次のようにします。

typedef std::list<int> IntList;
InstList list = <your_values>;

int top[3];
for (size_t i = 0; i < 3; i++)
    top[i] = std::numeric_limits<int>::min();

IntList::iterator it, end;
for (it = list.begin(), end = list.end(); it != end; ++it) {
    const int& value = *it;
    if (value > top[2]) {
        top[0] = top[1];
        top[1] = top[2];
        top[2] = value;
    } else if (value > top[1]) {
        top[0] = top[1];
        top[1] = value;
    } else if (value > top[0]) {
        top[0] = value;
    }
}

Answer 2

おそらく、の使用を検討してくださいpriority_queue。

Answer 3

基本的な考え方は、並べ替えられたリスト、優先キュー、または正確なN数値のヒープを維持することです。リストの最初の値をそれにプッシュNし、残りを繰り返します。キュー (または何でも) の最小値よりも大きいアイテムに遭遇した場合、その要素を削除して新しい要素をプッシュします。

のみを探している場合N=3は、プライオリティ キューなどよりも単純な配列を使用する方がよいでしょう。2 つの比較だけで、その配列内のどの要素が最小であるかを判断できます。最小要素のインデックスを常に覚えておいて、それを置き換えたときにのみ更新します。

興味深いことに、このアプローチでは、昇順で並べ替えられたリストのパフォーマンスが最悪になります。ただし、本質的に線形時間の複雑さは変わりません。