找到比Brute Force算法更好的

Question

问题如下：给定每个员工E的人员姓名，身高和体重的数据流，找到更高，体重超过E的员工组。

显然，这可能是强迫O（n ^ 2）。这是你能做的最好的吗？如果可以做得更好，算法会是什么？

Answer 1

如果我们在每个员工(height_i, weight_i)的2D平面上绘制点i，则员工i的查询变为2D正交范围查询，即在该矩形height_i < height <= height_max和weight_i < weight <= weight_max内找到点。

从wiki [1]，你可以得到一个时间复杂度为O(n log log n + k)的算法，其中k是输出的大小。

编辑：在最坏的情况下，k可以按照n^2的顺序

1：https://en.wikipedia.org/wiki/Range_searching#Orthogonal_range_searching

Answer 2

如果您对高度或重量的输入进行排序，您可以只检查每个条目的后续条目，因此您可以执行(l-1) + (l-2) + (l-3) + ... + 1比较而不是l * (l - 1)。不过，显然这仍然是二次方的。正如Ruakh在他们的评论中指出的那样，输出大小告诉我们这是我们能做的最好的事情（想象一下排序列表中的每个人都比较矮，每个人的重量都比后来的人少）。