3

これはインタビューの質問です: 、、および でSetクラスを実装します。getputgetRandom

次のオプションを検討します。

  • ソート済み/未ソートの連結リスト: get- O(N), put- O(N), getRandom- O(N)
  • ソートされていないベクトル (サイズ変更可能な配列): get- O(N), put- ?, getRandom- O(1)
  • ソートされたベクトル (サイズ変更可能な配列): get- O(logN), put- ?, getRandom- O(1)
  • ハッシュテーブル: get- O(1), put- O(1), getRandom- O(テーブルサイズ)
  • 平衡二分探索木: get- O(logN), put- O(logN), getRandom- O(N)

最良の候補は次のようです。

  • get/putよりもはるかに頻度が高い場合は、ハッシュ テーブルgetRandom
  • getRandomよりもはるかに頻繁な場合は、並べ替えられたベクトル (サイズ変更可能な配列)get/put

ベクトルとハッシュ テーブルを何らかの方法で組み合わせて、より良いセットを構成できないかと考えています。

4

3 に答える 3

1

ハッシュ テーブルの各バケットにいくつの項目があるかを示す別の構造を保持している場合、二分探索を使用して n 番目の要素を見つけることができます。これにより、3 つの操作すべてで O(log n) が得られます。

各ノードの「カウント」（このノードをルートとするサブツリーを持つノードの数を示す）で拡張されたバランスの取れた二分探索ツリーは、これらの境界に対しても機能します。

上記のいくつかの修正: リンクされたリストではランダム アクセスを実行できないため、すべての操作は O(N) です。また、並べ替えられたバージョンでは要素を置換する必要があり、並べ替えられていないバージョンでは重複をチェックする必要があるため、両方のベクトルで put は O(n) です。

于 2012-06-16T19:26:57.927 に答える
0

find ~O(1)
delete ~O(1)
add ~O(1)
Random の場合、すべての要素を持つ配列を使用し、ランダムな要素 O(1) を選択します

#include <stdio.h>
#include <vector>
#define MOD 666013
using namespace std;

int N;
vector<int> G[MOD];

vector<int>::iterator find(int x)
{
    int list=x%MOD;                  // f(i) = i % MOD this is my hash function
    vector<int>::iterator it;

    for (it=G[list].begin();it!=G[list].end();++it)
        if (*it==x)
            return it;
    return G[list].end();
}

void add(int x)
{
    int list=x%MOD;                     //again this is my hash function that gives me the key
    if (find(x)==G[list].end())
        G[list].push_back(x);
}

void delete(int x)
{
    int list=x%MOD;
    vector<int>::iterator it=find(x);

    if (it!=G[list].end())
        G[list].erase(it);
}
于 2012-06-16T19:19:48.640 に答える