首页 > 代码库 > Median of Two Sorted Arrays问题
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)).
样例1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
样例2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
看到这道题我就想到了归并排序中归并的过程,比较智障的是我没注意到题目给的是两个已排序的数组,我还用快排去排序了...
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) { int arr[10000]; int i=0,j=0,k=0,mid; while(k<nums1Size+nums2Size&&i<nums1Size&&j<nums2Size) arr[k++]=(nums1[i]<=nums2[j])?(nums1[i++]):nums2[j++]; if(i>=nums1Size){ while(j<nums2Size) arr[k++]=nums2[j++]; } else if(j>=nums2Size){ while(i<nums1Size) arr[k++]=nums1[i++]; } mid=(nums1Size+nums2Size)/2; return (nums1Size+nums2Size)%2==0?(double)(arr[mid]+arr[mid-1])/2:(double)arr[mid];}
这应该算是比较naive的算法了,把两个有序数组合为一个有序数组,再输出这个数组的中位数。
这个算法是O(max(m,n))的复杂度,显然不是出题人想要的O(log(m+n))。
不知道如何写出O(log(m+n))的算法,于是我看了下LeetCode的讨论区,有了一点灵感。
要求有序数组A和B的中位数,还是得把A和B重新划分为数组a和b,并且要做到a和b大小相同,且a中元素小于等于b中元素,这样剩下的那个元素或者a中最大元素与b中最小元素的算数平均数就是要求的中位数。关键是如何划分得到数组a和b呢,把A和B合并为一个新数组是一种划分的办法,不过太慢了。可以用i将A划分为[0,i)和剩余两部分,同样用j将A划分为[0,j)和剩余两部分。a和b分别由新划分得到的四个部分中的两个部分组成。确切地说a由A[0,i)和B[0,j)组成,b由剩余部分组成。因为a和b大小要相同,所以i+j==(m+n)/2,即j==(m+n)/2-i,所以现在问题变成了求i使得i满足A[i-1]<=B[j]&&B[j-1]<=A[i],其中j为(m+n)/2-i。(值得一提的是,m+n是奇是偶并不影响划分,因为(m+n)/2会自动舍位)
这时候原问题就变成了一个查找问题,因为数组已被排序,果断二分查找啊。
Median of Two Sorted Arrays问题