arrays - 如何处理不熟悉的算法（合并排序数组的第 k 个元素）

Question

我最近被分配了一个家庭作业问题，即在 O(lgk) 时间内找到一组合并的排序不同数组的第 k 个元素。为了完成这项工作，我不得不参考很多在线解决方案。让我烦恼的是，我必须首先引用它们。你如何处理这样的问题？我希望能够开发新的算法并使它们更有效率。我只需要研究 leetcode 就可以学习一百万种方法吗？我在基本层面上理解分而治之，但弄清楚它如何在这里应用完全超出了我的范围。我写了一个可以在 O(k) 时间内工作的方法，但这没有帮助。

问题详细：

假设您有两个单独的数字排序数组 A[1 ... m] 和 B[1 ... n]，其中 A 和 B 中的所有数字都是不同的。给定一个整数 k，其中 1 ≤ k ≤ m + n，设计一种算法，在 O(lg k) 时间内找到数组 A 和 B 合并中​​的第 k 个最小元素。

标签： arraysalgorithm