如何在两个排序数组的并集中找到第k个最小元素？

Question

这是一个作业问题。他们说这需要O(logN + logM)在哪里N，M是数组的长度。

让我们命名的数组a和b。显然，我们可以忽略所有a[i]和b[i]其中i>ķ。
首先，我们比较a[k/2]和b[k/2]。让b[k/2]> a[k/2]。因此，我们也可以丢弃所有b[i]，其中i> k / 2。

现在我们有了a[i]i <k和all> b[i]i <k / 2的全部，以找到答案。

你下一步怎么做？

Answer 1

您已掌握，继续前进！并注意索引...为了简化一点，我将假设N和M> k，因此这里的复杂度为O（log k），即O（log N + log M）。伪代码：i = k/2j = k - istep = k/4while step > 0&nbsp; &nbsp; if a[i-1] > b[j-1]&nbsp; &nbsp; &nbsp; &nbsp; i -= step&nbsp; &nbsp; &nbsp; &nbsp; j += step&nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; i += step&nbsp; &nbsp; &nbsp; &nbsp; j -= step&nbsp; &nbsp; step /= 2if a[i-1] > b[j-1]&nbsp; &nbsp; return a[i-1]else&nbsp; &nbsp; return b[j-1]为了演示，您可以使用循环不变i + j = k，但我不会做所有作业：)

Answer 2

自问这个问题以来已经过去了一年多，我希望我不回答您的作业。这是尾部递归解决方案，将花费log（len（a）+ len（b））时间。假设：输入正确。即k在[0，len（a）+ len（b）]范围内基本案例：如果数组之一的长度为0，则答案为第二个数组的第k个元素。减少步骤：如果中指a+中指b小于k如果的中间元素a大于的中间元素b，我们可以忽略的前一半b，进行调整k。否则忽略上半年的a调整k。否则，如果k小于和的中间索引之a和b：如果中的元素a大于中的元素b，我们可以放心地忽略中的后一半a否则我们可以忽略 b码：def kthlargest(arr1, arr2, k):&nbsp; &nbsp; if len(arr1) == 0:&nbsp; &nbsp; &nbsp; &nbsp; return arr2[k]&nbsp; &nbsp; elif len(arr2) == 0:&nbsp; &nbsp; &nbsp; &nbsp; return arr1[k]&nbsp; &nbsp; mida1 = len(arr1)/2&nbsp; &nbsp; mida2 = len(arr2)/2&nbsp; &nbsp; if mida1+mida2<k:&nbsp; &nbsp; &nbsp; &nbsp; if arr1[mida1]>arr2[mida2]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return kthlargest(arr1, arr2[mida2+1:], k-mida2-1)&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return kthlargest(arr1[mida1+1:], arr2, k-mida1-1)&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; if arr1[mida1]>arr2[mida2]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return kthlargest(arr1[:mida1], arr2, k)&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return kthlargest(arr1, arr2[:mida2], k)请注意，我的解决方案是在每次调用中创建较小数组的新副本，只需在原始数组上传递开始和结束索引即可轻松消除这种情况。