7

構造体への値の任意の挿入を高速（O（N）より高速）にできるデータ構造（配列のような）を探しています。データ構造は、挿入された方法で要素を出力できる必要があります。これは、ランダムアクセスや削除が必要ないことを除けば、List.Insert（）（すべての要素をシフトする必要があるため遅すぎる）のようなものに似ています。挿入は常に「配列」のサイズ内になります。すべての値は一意です。他の操作は必要ありません。

たとえば、Insert（x、i）がインデックスi（0-インデックス）に値xを挿入する場合。それで：

  • Insert（1、0）は{1}を与えます
  • Insert（3、1）は{1,3}を与えます
  • Insert（2、1）は{1,2,3}を与えます
  • Insert（5、0）は{5,1,2,3}を与えます

そして、最後に{5,1,2,3}を印刷できる必要があります。

私はC++を使用しています。

4

7 に答える 7

9

スキップリストを使用します。別のオプションは、階層化されたベクトルである必要があります。スキップリストは、const O（log（n））で挿入を実行し、番号を順番に保持します。階層化されたベクトルは、O（sqrt（n））での挿入をサポートし、要素を順番に出力できます。

編集：amitのコメントに従って、スキップリストでk番目の要素をどのように見つけるかを説明します。

要素ごとに、次の要素へのリンクに塔があり、リンクごとに、ジャンプする要素の数がわかります。したがって、k番目の要素を探すには、リストの先頭から始めて、k個の要素を超えないリンクが見つかるまでタワーを下ります。このノードが指すノードに移動し、ジャンプした要素の数に応じてkを減らします。k = 0になるまで、これを続けます。

于 2012-04-06T12:37:49.543 に答える
1

あなたのコメントについて：

List.Insert（）（すべての要素をシフトする必要があるため、遅すぎます）、

リストは値をシフトしません。リストを繰り返し処理して、挿入する場所を見つけます。言うことに注意してください。これは私のような初心者には混乱を招く可能性があります。

于 2012-06-05T18:46:33.283 に答える
1

値へのマッピング（インデックス、挿入時間）のペアを使用できstd::mapます。ここで、挿入時間は「自動インクリメント」整数（SQL用語）です。ペアの順序は次のようになります

(i, t) < (i*, t*)

iff

i < i* or t > t*

コード内：

struct lt {
    bool operator()(std::pair<size_t, size_t> const &x,
                    std::pair<size_t, size_t> const &y)
    {
        return x.first < y.first || x.second > y.second;
    }
};

typedef std::map<std::pair<size_t, size_t>, int, lt> array_like;

void insert(array_like &a, int value, size_t i)
{
    a[std::make_pair(i, a.size())] = value;
}
于 2012-04-06T12:49:35.833 に答える
1

またはの使用を検討しましたstd::map かstd::vector？

std::map挿入のランクをキーとして使用できます。また、vectorにはreserveメンバー関数があります。

于 2012-04-06T12:37:17.340 に答える
1

デフォルトでGCCに含まれているソリューションは、ロープデータ構造です。これがドキュメントです。通常、長い文字列を操作するときにロープが思い浮かびます。ここでintは文字の代わりにsがありますが、同じように機能します。intテンプレートパラメータとして使用するだけです。pair（ sなどの場合もあります）

ウィキペディアのロープの説明は次のとおりです。

基本的に、これは左右のサブツリーにある要素の数（または順序統計と呼ばれる同等の情報）を維持するバイナリツリーであり、要素が挿入および削除されるときにサブツリーがローテーションされると、これらのカウントが適切に更新されます。これにより、O（lg n）操作が可能になります。

于 2016-05-05T12:00:42.450 に答える
0

挿入時間をO（N）からO（sqrt（N））に短縮するこのデータ構造がありますが、私はそれほど感銘を受けていません。もっと上手くやれるはずなのに、少し頑張らなきゃいけないなぁと思います。

于 2021-11-04T20:44:51.700 に答える
-1

C ++では、次のようにベクトルのマップを使用できます。

int main() {
  map<int, vector<int> > data;
  data[0].push_back(1);
  data[1].push_back(3);
  data[1].push_back(2);
  data[0].push_back(5);
  map<int, vector<int> >::iterator it;
  for (it = data.begin(); it != data.end(); it++) {
    vector<int> v = it->second;
    for (int i = v.size() - 1; i >= 0; i--) {
      cout << v[i] << ' ';
    }
  }
  cout << '\n';
}

これは印刷します：

5 1 2 3

必要に応じて、挿入はO（log n）です。

于 2012-04-06T12:46:31.320 に答える