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

5

你可以做get，put而且getRandom都是O(1)平均时间。

您所做的是存储 2 个数据结构。一个是哈希。另一个以可增长数组中的随机顺序列出元素。

当你put，你把它放在散列中，将元素添加到数组的末尾，然后将数组的末尾交换为随机数组元素。

当 you 时get，您会在哈希中查找元素。

当你 时getRandom，你取数组的最后一个元素，然后将最后一个元素与数组中的另一个位置交换。

如果你愿意，你可以添加delete只是删除哈希。现在getRandom通过获取元素来实现，检查它是否在散列中，如果不在则缩小数组，然后重复。在这一点getRandom上偶尔O(n) 但所有操作的摊销平均成本可以被证明是O(1)。

于 2012-06-16T19:51:49.350 回答
1

如果您保留一个单独的结构来告诉您哈希表的每个存储桶中有多少项目，您可以使用二进制搜索来查找第 n 个元素，这将为您提供所有三个操作的 O(log n)。

为每个节点增加一个“计数”的平衡二叉搜索树（告诉有多少节点的子树以该节点为根）也适用于这些边界。

对上述内容的一些更正：您不能在链表中进行随机访问，因此所有操作都是 O(N)。此外，由于必须替换已排序版本中的元素并检查未排序版本中的重复项，因此在两个向量中的 put 都是 O(n)。

于 2012-06-16T19:26:57.927 回答
0

find ~O(1)
delete ~O(1)
add ~O(1)
对于随机我们使用包含所有元素的数组并选择一个随机元素 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 回答