algorithm - 来自一组区间的第 K 个最小值

Question

您已经给出了一组间隔，例如 {2,7} 、 {3,8} 、 {9,11} 、 {-4,-1} 等等。问题是从这些间隔集中找到第 k 个最小值。

重复项也被计算两次。例如，如果间隔是 {1,4} 和 {2,6} 并且 k = 3 那么答案是 2 因为如果我们拉平间隔并排序合并它们然后我们得到序列

 1,2,2,3,3,4,4,5,6

第 3 分钟是 3。

可以有很多方法来解决这个问题。但是，我正在努力寻找时间/空间复杂度最低的那个。

Answer 1

1. 拉平间隔。
2. 对展平序列进行排序。
3. 迭代排序序列，直到找到第 k 个元素，同时忽略重复值。

---

现在让我们做一些分析，我们设置 N 间隔中出现的总数和 M 一个数字将具有的重复值的平均数量(将对于唯一的展平序列为 1)。

空间复杂度:

O(N)

如果您有很多重复元素，您可以在哪些方面做得更好，方法是遍历展平序列，同时丢弃重复元素。

时间复杂度:

O(k*M + NlogN)

• 扁平化需要 O(N)
• 排序需要 O(NlogN)
• 迭代需要 O(k*M)