0

正如标题中所说，我需要定义一个数据结构，它只需要 O(1) 时间来插入删除和 getMIn 时间......没有空间限制......

我已经搜索过相同的内容，而我发现的只是在 O(1) 时间内进行插入和删除......即使是堆栈也是如此。我在堆栈溢出中看到了以前的帖子，他们所说的都是散列......

通过我在 O(1) 时间内对 getMIn 的分析，我们可以在 O(1) 时间内使用堆数据结构
进行插入和删除，我们有堆栈......

所以为了实现我的目标，我认为我需要围绕堆数据结构和堆栈进行调整......我将如何在这种情况下添加散列技术......

如果我使用哈希表，那么我的哈希函数应该是什么样子如何在哈希方面分析情况......任何好的参考将不胜感激......

4

6 回答 6

2

如果您最初假设插入和删除是 O(1) 复杂性（如果您只想插入顶部并从顶部删除/弹出，那么堆栈可以正常工作），那么为了让 getMin 返回最小值在恒定时间内，您需要以某种方式存储最小值。如果您只有一个成员变量来跟踪 min 那么如果将其从堆栈中删除会发生什么？您将需要下一个最小值，或相对于堆栈中剩余内容的最小值。为此，您可以让堆栈中的元素包含它认为的最小值。堆栈在代码中由链表表示，因此链表中节点的结构如下所示：

struct Node
{
  int value;
  int min;
  Node *next;
}

如果您查看示例列表：7->3->1->5->2。让我们看看这将如何构建。首先将值 2 推入（到空堆栈），这是最小值，因为它是第一个数字，跟踪它并在构造它时将其添加到节点：{2, 2}。然后你将 5 压入堆栈，5>2 所以最小值是相同的压入 {5,2}，现在你有 {5,2}->{2,2}。然后你推入 1，1<2 所以新的最小值是 1，推 {1, 1}，现在是 {1,1}->{5,2}->{2,2} 等等。到最后你有：

{7,1}->{3,1}->{1,1}->{5,2}->{2,2}

在这个实现中，如果你弹出 7、3 和 1，你的新最小值应该是 2。而且您的所有操作仍处于恒定时间，因为您只是向节点添加了一个比较和另一个值。（您可以使用 C++ 的 peek() 之类的东西，或者只使用指向列表头部的指针来查看堆栈顶部并在那里获取最小值，它会在恒定时间内为您提供堆栈的最小值）。

这个实现的一个折衷是你的节点中有一个额外的整数，如果你在一个非常大的列表中只有一两分钟，那就是浪费内存。如果是这种情况，那么您可以在单独的堆栈中跟踪分钟，只需将要删除的节点的值与该列表的顶部进行比较，如果匹配，则将其从两个列表中删除。要跟踪的事情更多，因此这实际上取决于情况。

免责声明：这是我在这个论坛上的第一篇文章，所以如果它有点令人费解或罗嗦，我很抱歉。我也不是说这是“一个真实的答案”，而是我认为最简单且符合问题要求的答案。总是有权衡，根据情况需要不同的方法。

于 2012-05-07T20:31:00.460 回答
2

这是一个设计问题，这意味着他们想看看你能多快地扩充现有的数据结构。

从你知道的开始：

  • O(1)更新，即插入/删除，在尖叫hashtable
  • O(1) getMin 也在尖叫哈希表，但这次是有序的。

在这里，我提出了一种方法。你可能会找到你喜欢的其他东西。

  • 创建一个HashMap，调用它main，存储所有元素的地方
  • 创建一个 LinkedHashMap（java 有一个），调用它mins来跟踪最小值。
  • 第一次将元素插入到main中时，也将其添加到mins。
  • 对于每个后续插入，如果新值小于地图头部的值mins，则将其添加到地图中，与addToHead.
  • 当您从 中删除一个元素时main，也将其从 中删除mins。2*O(1) = O(1)
  • 请注意，这getMin只是偷看而不删除。所以只是偷看的头mins。

编辑：

摊销算法：

（感谢@Andrew Tomazos - Fathomling，让我们玩得更开心！）

我们都知道插入哈希表的成本是 O(1)。但实际上，如果您曾经构建过哈希表，您就会知道必须不断将表的大小增加一倍以避免溢出。每次将包含 n 个元素的表的大小加倍时，都必须重新插入元素，然后添加新元素。通过这种分析，将元素添加到哈希表的最坏情况成本似乎是 O(n)。那么为什么我们说它是 O(1) 呢？因为并非所有元素都采取最坏的情况！实际上，只有发生加倍的元素才会出现最坏情况。因此，插入 n 个元素会n+summation(2^i where i=0 to lg(n-1))得到n+2n = O(n)这样的结果O(n)/n = O(1)！

为什么不对linkedHashMap 应用同样的原则呢？无论如何，您必须重新加载所有元素！因此，每次加倍时，也要以分钟为main单位放入所有元素，并将它们排序为. 然后对于所有其他情况，按上述方法进行（项目符号步骤）。mainmins

于 2012-05-07T21:02:21.027 回答
0

哈希表让您在 O(1) 中插入和删除（堆栈没有，因为堆栈中不能有孔）。但是您也不能在 O(1) 中使用 getMin ，因为对元素进行排序不能比 O(n*Log(n)) 快（这是一个定理），这意味着每个元素的 O(Log(n))元素。

您可以保留一个指向最小值的指针以使 getMin 在 O(1) 中。这个指针可以很容易地为插入而更新，但不能为 min 的删除而更新。但取决于您使用删除的频率，这可能是一个好主意。

于 2012-05-07T10:04:42.610 回答
0

严格来说，您所说的问题可能是不可能的，但请考虑以下事项：

给定一个类型 T 对该类型的所有可能元素进行枚举，使得当 T(i) < T(j) 时值 i 小于值 j。（即按顺序编号 T 类型的所有可能值）

创建一个该大小的数组。

制作数组的元素：

struct PT
{
   T t;
   PT* next_higher;
   PT* prev_lower;
}

将元素插入和删除元素到维护双链表的数组中（按索引顺序，因此按排序顺序）存储

这将为您提供恒定的 getMin 和删除。

对于插入，您需要在恒定时间内找到数组中的下一个元素，所以我会使用一种基数搜索。

如果数组的大小为 2^x，则维护 x 个“跳过”数组，其中数组 i 的元素 j 指向要索引的主数组的最近元素 (j << i)。

然后，这将始终需要固定 x 数量的查找来更新和搜索，因此这将提供恒定的时间插入。

这使用指数空间，但这是问题要求所允许的。

于 2012-05-07T10:10:47.263 回答
0

您可以使用trie。trie 对于插入、删除和 getmin 都有 O(L) 复杂性，其中 L 是您要查找的字符串（或其他）的长度。它相对于 n（元素的数量）具有恒定的复杂性。

但是，它需要大量的内存。当他们强调“没有空间限制”时，他们可能正在考虑尝试。:D

于 2012-05-07T10:21:53.240 回答
-1

在您的问题陈述中“在 O(1) 时间内插入和删除我们有堆栈......”所以我假设在这种情况下删除 = pop()，使用另一个堆栈来跟踪 min

algo: Stack 1 -- 普通栈；堆栈 2 -- 最小堆栈

插入

推入堆栈 1。如果堆栈 2 为空或新项目 < stack2.peek()，则也推入堆栈 2

目标：在任何时候 stack2.peek() 应该给你最小 O(1)

删除

从堆栈 1 中弹出（）。如果弹出的元素等于 stack2.peek（），则从堆栈 2 中弹出（）

于 2012-05-08T10:56:56.463 回答