K'th Min从一组间隔

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.

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

Answer 1

1. 平放间隔。
2. 排序扁平序列。
3. 遍历已排序的序列，直到找到第k个元素， 而忽略重复值。

---

现在让我们做一些分析，这里我们设N出现在你的间隔M总数的数量重复值的平均数目多少都会有（将1独特的扁平化序列） 。

空间复杂：

O（N）

在那里你可以做的更好，如果你有很多重复的元素，通过循环扁平化序列，而丢弃重复的元素。

时间复杂度：

O（K * M + NlogN）

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