在c ++映射中查找与最大值对应的键

Question

给定一个数字 'KEY' 和 map myMap。我试图在地图 myMap 中找到最小的键 k（条件：k < KEY），使其值最大。

示例：

map <int, int> myMap = {{3,1}, {4,3}, {5,2}, {6,3}, {7,2}, {8,5}};
                             // ^^^
int KEY = 7;

答案是4，因为对于所有小于7(KEY)的键，键4和键6的最大值都是3。4是最小的键。

地图是动态增加的，有几个这样的KEY查询

我想在 O(logN) 时间内得到 {k,v} 对

我在使用 lower_bound 后卡住了。使用下限给我 max 'k' 这样 k < KEY。在上面的示例中，我可以通过 KEY=7 获得 {7,2}。但努力在 logN 时间内到达 {4,3}。是否有任何数据结构可以帮助我在 logN 时间内实现此目标？

更新：

我也确保以对数时间对地图进行更新。整数不超过 10^5。是否可以使用其他一些数据结构和方法（在这种情况下它看起来像动态 programming/binary 搜索）在对数时间内解决这个问题？

Answer 1

Is there any data structure which can help me achieve this in logN time?

除非您能够以有意义的方式组合这些值，否则不会。所有（几乎）log N 算法都依赖于分而治之的方法。

你基本上有两个不相关的序列。树映射的键允许你做 log N 的事情，但你需要对非结构化序列进行另一次搜索，这是 O(N)。

因此，要在 O(log N) 上完成此操作，您需要以某种方式组合键和值，或者使用 @Igor 建议的路线评论，这实际上是一张地图。

当然，调整实施可能会带来好处，但不会带来 O(N) -> O(log N) 类型的好处。

Answer 2

这个怎么样。您维护一个辅助地图，它是您的主要地图的一个子集。具体来说，当且仅当主映射中的所有较小键都对应于较小的值时，此辅助映射将包含 {k, v}。

对于您的 {3,1}, {4,3}, {5,2}, {6,3}, {7,2}, {8,5} 示例，此辅助地图将是 {3,1}, {4,3}, {8,5}。观察值如何随键单调递增。

如何使用这张地图来回答问题应该很明显 - 只需使用 lower_bound 查找密钥即可。在示例中，对于键 7，查找将找到 4，即正确答案。

现在，如何维护这张地图。当您将 {k, v} 插入主地图时，使用 lower_bound 在辅助地图中查找 k。有两种可能：

存在一个较小的键值相等或较大。什么都不做，副图不用更新
不存在更小的键，或者更小的键对应更小的值。然后
- 将{k, v}插入副图
- 按顺序遍历键，从 k 开始，直到遇到具有较大值的键 k'，或到达终点。擦除 k 和 k'（不包括两者）之间的范围，或从 k（不包括）到结尾。

从表面上看，这最后一步看起来是线性的 - 但实际上它是摊销常数。在 N 次插入中，此步骤最多必须遍历 2*N 个元素（例如，第一个 N-1 个步骤分别插入一个元素，最后一步将它们全部删除并插入一个）。

Finding key corresponding to max value in c++ map