4

匹配数据最有效的数据结构是什么？例如，假设我看到以下场景：

<time available> <buy or sell> <company name> <buy or sell price> <amount to buy or sell>

这样一个文件可能包含：

0 sell yahoo $100 #1
2 sell yahoo $14  #1
2 sell yahoo $28  #1
.. 95 other yahoo sells <$125 and amount #1
3 sell yahoo $17  #1
5 sell yahoo $33  #1
9 buy yahoo  $125 #100

是否可以在 O(n) 时间内将最后一次买入与前 100 次卖出相匹配，其中 n = 100 如果要与与其想要购买的公司相对应的最低售价匹配（或在平局的情况下首先出现）？

我知道一个天真的解决方案是对列表进行排序并按顺序进行，但这需要比 O(n) 时间更长的时间。处理这个问题以及与之类似的最有效的数据结构是什么？

4

2 回答 2

2

尝试使用从公司名称到一堆卖单的哈希映射，按价格排序。现在插入卖单O(log n)，如果买单没有用完卖单，或者O(log n)如果用完（您的问题陈述未指定） ，则买单将保持不变

于 2013-03-24T22:17:07.380 回答
0

由于买卖将处理同一个组织，因此最好将所有买入（或）卖出记录保存在地图中，就像所有雅虎记录都保存在一个列表中，该列表以“雅虎”为键散列到地图中，这可以最大限度地减少您的搜索空间。对时间戳、价格、数量进行排序，然后您可以在插入时通过实现此结构以最优成本实现所需的功能。然后，在此之后的任何查询都应该花费更少的时间，因为搜索空间很小。

于 2013-03-25T12:49:07.013 回答