7

私は、最小限の時間で（最悪の場合）私のニーズを満たす単純な実装されたデータ構造を探していました:-

（1）n番目の要素をポップするには（要素の相対的な順序をそのまま維持する必要があります）
（2）n番目の要素にアクセスするには。

配列はポップできず、 i 番目の要素を削除した後にギャップを作りたくないため、使用できませんでした。n番目の要素を次の要素と次の最後まで交換することでギャップを取り除こうとしましたが、配列のO(1)は無敵ですが、それは時間の効率が悪いことを証明しています。

vector を使用してみて、 popup に「erase」を使用し、 access に「.at()」を使用しましたが、これでも array よりは優れていますが、時間効率の点で安くはありません。

4

4 に答える 4

3

さて、配列に実装された階層化されたベクトルは、あなたの目的に最も適していると思います。階層化されたベクトルの概念は、最初は知っていて理解するのが少し難しいかもしれませんが、一度理解すると、多くの質問が開かれ、多くの質問のデータ構造部分に非常に効率的に取り組むための便利な武器が得られます。したがって、階層化されたベクトルの実装をマスターすることをお勧めします。

于 2012-11-03T04:59:31.047 に答える
3

試すことができるのはスキップリストです-O（log（n））で要求している操作をサポートしています。別のオプションは、実装が少し簡単で、O(sqrt(n)) を取る階層型ベクトルです。どちらの構造も非常にクールですが、残念ながらあまり人気がありません。

于 2012-10-19T14:47:58.857 に答える
2

配列を使用すると、要素をO(1)検索してO(n)削除できます。リストは、要素のO(n)バグO(1)削除の検索を提供します。

二分探索木は、要素を削除してO(log n)ルックアップを提供します。O(1)ただし、相対的な順序は保持されません。

リストと組み合わせて使用​​される二分探索木は、両方の長所を提供します。リスト (順序を維持するため) とツリー (高速ルックアップ) の両方にノードを挿入します。削除となりますO(1)。

struct node {
   node* list_next;
   node* list_prev;
   node* tree_right;
   node* tree_left;

   // node data;
};

インデックスをソート値として使用してノードをツリーに挿入すると、ツリーのふりをした別のリンク リストが作成されることに注意してください。ツリーは、一度だけ発生する必要がある構築された後、時間内にバランスをとることができます.O(n)

アップデート

これについてもっと考えてみると、これはあなたにとって最善のアプローチではないかもしれません。私は、セット内の相対位置ではなく、データ自体を検索することに慣れています。これはデータ中心のアプローチです。「より高い」インデックスを変更する必要があるため、ノードを削除するとすぐにインデックスをソート値として使用すると壊れます。

于 2012-10-19T14:46:57.533 に答える
0

警告: この回答を真剣に受け止めないでください。

理論的には、O(1) で両方を実行できます。これが最適化する唯一の操作であると仮定します。次のソリューションでは、大量のスペースが必要になり (スペースがリークします)、データ構造の作成に時間がかかります。

配列を使用します。配列のすべてのエントリで、同じであるがそのエントリが削除された別の配列をポイントします。

于 2012-10-19T19:38:12.247 に答える