algorithm - 如何在 O(nlogn) 时间复杂度内完成

Question

我的考试有一个问题，我必须想出一个有效的算法。问题是这样的:

我们有一些对象有两个属性:

H = <1,1000000> 
R = <1,1000000>

如果 H1>H2 和 R1>R2，我们可以将一个对象插入到另一个对象中。输入包含一对 H 和 R，每行一对。如果当前对象可以插入任何先前的对象中，我们选择具有最少 H 的对象，然后我们销毁它们。在输出中打印剩余对象的数量。

我想知道如何使用二叉搜索树或线段树或芬威克树在 O(n.log(n)) 时间复杂度内解决这个问题。

提前致谢。

Answer 1

采用fenwick tree的解决方案，如下；

• 让我们首先按 R 对整个数组进行排序(现在，我们不关心 H)，并为每个项目分配一个标记(等于它的排序数组中的位置)。
• 让我们回到原来的数组。我们将对给定的数组进行扫描。比如说，我们有一个 fenwick 树，它将只存储 H 的最大值(从开始到该位置)，而不是累积和。
• 例如，对于一个项目，我们无法将它放入另一个项目中。然后我们将它插入到树中。我们将插入等于它的 token 的位置。
• 所以，现在，我们有一个 fenwick 树，它只包含我们到目前为止处理过的项目。其他值为 0。树中的项目按 R 排序顺序定位。
• 现在，如何确定我们是否可以将当前项适合另一个对象？我们实际上可以在 fenwick 树上对当前项的 H 运行二分搜索(上限)。而且，由于项目已经按 R 顺序排序，而不是整棵树，我们需要在有效范围内搜索。
• 芬威克树中的二分查找可以在 O(log(n)) 中完成。查看 this 的查找具有给定累积频率的索引部分文章。