algorithm - 在大小为 m 和 n 的 2 个排序列表的并集中找到第 k 个最小元素，效率为 log(k)

Question

在大小为 m 和 n 的 2 个已排序列表的并集中查找第 k 个最小元素

通过效率log(k)，我做了很多思考和搜索，我也得到了

pesedocode 及其解释...到目前为止我仍然不明白或不理解

问题是正确的..任何帮助将不胜感激....

Answer 1

所以你必须设置，比如 { 1, 4, 5, 7, 8, 12, 98, 1993 }和{ 2, 5, 8, 10, 88 } 。 你想找到第三小的元素。

这意味着 m=8、n=5 和 k=3。 目视检查这些集合，您会发现答案是 4。 您的查找算法必须在 O(log(k)) 内找到正确的值(即“大O”)。

这意味着如果您的算法通过多个步骤找到元素 N = n1 + n2 + ... ，其中每个 n1, n2, ...是 k 的函数，即所有 n1, n2... 的增长率必须小于或等于 log(k) 的增长率。

如果这没有意义，则目标是在少于 k 步的时间内找到该元素(其中 k > 1)。