面试 Eleme 的一道算法题。
给两个有序数组，找出中间值。
我的方案... , 查了下资料。
关键点， 就是中间值有什么用。
中间值可以把一个有序集合一分为二，左边的值总比右边的小。
现在是两个数组的中间值，
用 i 拆分第一个数组，
left_A | right_A
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
用 j 拆分第二个数组，
left_B | right_B
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
接着做一个合并， 小的都放左边， 大的都放右边。
left_part | right_part
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
如果满足这两个条件，
len(left_part)=len(right_part)
max(left_part)≤min(right_part)
现在两个数组的中间值，就出来了
max(left_part)+min(right_part) 的一半
然后就是找出 满足条件的 i
充分利用规则， 找到合适的点， 就可以了
LeetCode 第 4 题， Median of Two Sorted Arrays
leetcode.com
给两个有序数组，找出中间值。
我的方案... , 查了下资料。
关键点， 就是中间值有什么用。
中间值可以把一个有序集合一分为二，左边的值总比右边的小。
现在是两个数组的中间值，
用 i 拆分第一个数组，
left_A | right_A
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
用 j 拆分第二个数组，
left_B | right_B
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
接着做一个合并， 小的都放左边， 大的都放右边。
left_part | right_part
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
如果满足这两个条件，
len(left_part)=len(right_part)
max(left_part)≤min(right_part)
现在两个数组的中间值，就出来了
max(left_part)+min(right_part) 的一半
然后就是找出 满足条件的 i
充分利用规则， 找到合适的点， 就可以了
LeetCode 第 4 题， Median of Two Sorted Arrays
leetcode.com
展开
评论
10
![[吐舌]](http://lf3-cdn-tos.bytescm.com/obj/static/xitu_juejin_web/img/jj_emoji_95.6b0752f.png)
![[流泪]](http://lf3-cdn-tos.bytescm.com/obj/static/xitu_juejin_web/img/jj_emoji_6.dde0d83.png)