algorithm - 选择和过滤算法

Question

我想从数据集中选择前 n 个值，但根据我已经选择的内容忽略元素 - 即给定一组点 (x,y)，我想选择 x 的前 100 个值(它们都是不同的)但不选择任何点使得 y 等于任何已经-的 y选定的点。我想确保优先考虑 x 的最高值。

是否有任何现有的算法，或者至少有类似的算法？我有大量数据，希望尽可能高效地执行此操作。内存不是那么重要。

Answer 1

您可以在 O(n log k) 时间内完成此操作，其中 n 是数据集中值的数量，k 是您想要获得的最高值的数量。

1. 将您希望排除的值存储在哈希表中。
2. 创建一个空的最小堆。
3. 遍历所有值和每个值:
   1. 如果它在哈希表中则跳过它。
   2. 如果堆中包含的值少于 k 个，则将其添加到堆中。
   3. 如果堆包含 >=k 个值，如果您正在查看的值大于最小堆的最小成员，则弹出该值并添加新值。