如何找到两个排序数组的并集中的第k个最小元素？
这是一个作业问题。他们说这需要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。
现在我们有了all a[i]，其中i <k和all b[i]，其中i <k / 2来找到答案。
你下一步怎么做？ 问题来源于stack overflow
展开
收起
1
条回答
写回答
写回答
-
您已掌握，继续前进！并注意索引...
为了简化一点，我将假设N和M> k，因此这里的复杂度为O（log k），即O（log N + log M）。
伪代码：
i = k/2 j = k - i step = k/4 while step > 0 if a[i-1] > b[j-1] i -= step j += step else i += step j -= step step /= 2
if a[i-1] > b[j-1] return a[i-1] else return b[j-1] 为了演示，您可以使用循环不变i + j = k，但我不会做所有作业：)
2020-02-08 11:20:44赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
