3

我被要求实现一个堆栈，该堆栈弹出面试中最常添加的项目。我给了他以下答案，但他对解决方案不满意。

class stack 
{
  // Map of value and count 
  map<int,int> Cntmap; 

  public: 
  void push(int val) 
  { 
    // Find val in map 

    // if found then increment map count 

    // else insert a pair (val,1) 
  } 

  int pop( ) 
  { 
    // Find the Key in Cntmap with max value 

    // using std::max_element 

    // Decrement the Cntmap count for the popped val 
  } 
}

任何人都可以帮助我正确的方法吗？

4

4 回答 4

3

这是一个有趣的问题，因为在 中push，您使用键查找，而在 中pop，使用映射的值。 std::map 立即支持第一个：您所要做的就是：

++ CntMap[ val ];

如果[]键不存在，则运算符将插入一个条目，并使用其默认构造函数初始化映射类型，这int会导致0. 你甚至不需要if.

第二个更难。然而，评论给出了解决方案：您所需要的只是一个 custom Compare，它需要两个 std::pair<int, int>，并比较第二个元素。 std::max_element将返回一个迭代器到您感兴趣的条目，因此您可以直接使用它。到目前为止一切都很好（而且非常简单），但是您必须考虑错误条件：如果Cntmap为空会发生什么。如果计数下降到，您可能希望删除元素0（同样，简单，因为您有一个迭代器指定条目，同时具有键和值）。

最后，如果这是一个面试问题，我肯定会指出pop操作是O(n)，并且维护二级索引可能是值得的（尽管要复杂得多），以便我可以更快地找到最大元素。（如果我在面试，那将是我的下一个问题。显然，对于高级程序员来说。）

于 2013-07-11T08:51:17.433 回答
1

仅使用单个（简单）数据结构的问题是其中一个操作必须是线性的（它必须搜索所有元素），这还不够好。在您的情况下，我相信线性时间操作是pop.

我的尝试：

  • 有一个链表（按频率排序）。

  • 有一个值到链表中节点的映射。

  • 要推送，请在地图中查找值以获取链表节点。

    • 如果找到，增加频率并适当移动节点以保持链表排序。

    • 如果未找到，请将频率设置为 1 并插入到链表中的适当位置。

  • 要弹出，减少链表第一个节点的频率并适当移动它以保持链表排序，并返回适用值。

如果有许多节点具有相同的频率，您可能会遇到一些非常糟糕的最坏情况行为。应该可以通过具有某种链接列表的链接列表来获得恒定的时间添加/递增/递减，大型链接列表中的每个节点代表一个特定的频率，并且从那里的每个链接列表代表所有节点那个频率。

通过上面的优化，pop 可以是 O(1)，push 可以是 O(log n)。如果您使用unordered_map(C++11)，则 push 可以是 O(1)。

另一个（可能稍微简单一点）的选择是做与上面类似的事情，但使用 aheap而不是链表。

于 2013-07-11T08:56:33.223 回答
0

我认为 Max-Heap 在您的情况下会更好，而不是 Map。您可以以类似的方式维护计数器。请注意，堆的键将是计数而不是实际值本身。当您必须插入一个值时，搜索该值，如果找到，增加它的键，否则，插入键为 1 的值。希望这会有所帮助。

于 2013-07-11T08:23:21.573 回答
0

解决方案可能是包装Boost.Bimap（组织是否使用 boost？）。有了这个，您可以创建一个容器，该容器在一个方向上提供有序访问并在另一个方向上进行散列。您对 push 和 pop 的实现将使用bimap 的替换功能。

于 2013-07-11T11:34:26.307 回答