algorithm - 用于数据匹配的高效数据结构

Question

匹配数据最有效的数据结构是什么？例如，假设我遇到以下情况:

<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) 更长的时间。处理这个问题和类似问题的最有效数据结构是什么？

Answer 1

尝试使用从公司名称到一堆卖单的 HashMap ，按价格排序。插入卖单现在是 O(log n)，如果买单没有用完卖单，则买单变为常量，或者 O(log n)如果是(你的问题陈述没有具体说明)