Algorithm: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)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
- Level: Hard
解题思路与状态
问题分析
- 已知条件
两个排序数组,数组num1,元素个数为m;数组num2,元素个数为n; - 问题
找到num1和num2的中位数 - 约束
算法的运行最坏时间为O(log(m+n))
解题思路
归并排序法
如果没有时间约束,就可以使用归并排序,若排序后的结果为nums3,元素个数为k=m+n;最终将问题转化为:
求数组nums3的中位数。
- 若k为奇数,直接为nums3[k/2];
- 若k为偶数,则为(nums3[k/2]+nums3[k/2-1])/2;
此解法的时间复杂度为O(m+n),主要是归并排序上;空间复杂度为O(m+n),用于暂存归并排序后的结果。
具体的代码如下:
1 | // find the median of a sorted arrray |
递归算法
目前递归算法还未写出来,断断续续思考使用递归的想法有几天了,一直未果。现在留着不写,后续解决
之后在补上。
总结
对于使用递归算法解决此问题没能解决,内心是十分痛苦的。目前的思路是能否借助于二分查找算法解决,
最为关键的是递归结束的条件是什么。
Author: cloudfeng
Link: https://cloudfeng.github.io/2018/06/29/arts/algorithm/A-Find-median/
License: 知识共享署名-非商业性使用 4.0 国际许可协议