LeetCode 4 Median of Two Sorted Arrays

题目链接:Median of Two Sorted Arrays

题意:给两个排好序的数组,求将两个数组合并之后的中位数。

 

可以把题目转换成求第k大的数。

采用二分的方法。从a,b两个数组的首部删去k/2个数(这里需要判断下边界,不能超出剩下数的数量),直到k==1或者某一个数组被删完。

判断a[k/2-1]与b[k/2-1]的大小

当a[k/2-1]<b[k/2-1],那么a[0]~a[k/2-1]都是属于前k个数,可以直接删去,这时k变为 \(\frac{k}{2}\)

当a[k/2-1]>b[k/2-1],同理

当a[k/2-1]==b[k/2-1],这时a数组可删的数+b数组可删的数=k,那么a[k/2-1]或者b[k/2-1]就是要找的中位数。

由此递归求解。

注意判断下总长度的奇偶,分类讨论下。

时间复杂度 \(O(log(n+m))\)

 

 

Categories: LeetCode