雅乐网

计算机技术、学习成长

编程 » OJ刷题 » 【OJ】【Leetcode】4. Median of Two Sorted Arrays

【OJ】【Leetcode】4. Median of Two Sorted Arrays

题目

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

Example 2:

思路

两个排序数组找中位数,如果用类似归并排序merge的方式可以找到中间的数字,时间复杂度为O(m+n)。

本题目要求时间复杂度为O(log(m+n)),只能考虑利用已排序的特点直接按下标寻值,而不是遍历。

n个数字寻找中位数需要寻找第n/2或者n/2和n/2+1两个位置的数字,关键是如何寻找两个数组的第k小元素。

先从两个数组中一共取出k个元素,第一个数组取第k1小,第二个数组取弟k2( = k – k1)小

这样就把两个数组分成了4个部分,其中A<B, C<D

如果v1 == v2,那么它的值就正好是第k小。

如果v1<v2,那么我们可以肯定第k小的元素不会在A中,类似的v1>v2时,可以排除C

这样就把问题的规模缩小了

代码

 

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/oj_leetcode_4_median-of-two-sorted-arrays.html

上一篇:

下一篇:

我要评论

验证码*: 2 + 8 =