国内最全IT社区平台 联系我们 | 收藏本站
阿里云优惠2流量王
您当前位置:首页 > php开源 > php教程 > leetcode No4. Median of Two Sorted Arrays

leetcode No4. Median of Two Sorted Arrays

来源:程序员人生   发布时间:2016-11-11 08:21:03 阅读次数:678次

Question:

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

求两个数组合并后的中位数

Algorithm:

中位数求法:把长度为k数组从小到大排列,返回中间位置的元素。
k为奇数,中位数为nums[k/2],k为偶数中位数为(nums[k/2]+nums[(k/2)⑴]/2
算法1:归并两个数组后,找中位数,复杂度O(m+n)
算法2:类似2分查找,不需要归并,复杂度O(log(m+n))
现在详细说明解法2,我们可以把问题转化为寻觅第k大的元素
假定AB的长度都大于k/2,比较A[(k/2)⑴]和B[(k/2)⑴],有3种情况
1、A[k/2⑴] = B[k/2⑴]
此时,我们就已找到第k大的元素,即element=A[k/2⑴]=B[k/2⑴]
2、A[k/2⑴] < B[k/2⑴]
此时,意味着A[0]~A[k/2⑴]都比第k个元素小,由于A[0]~A[k/2⑴]有k/2个元素,B[0]~B[k/2⑴]有k/2个元素,如果A[k/2⑴]是比第k个元素还大的元素,假定A[k/2⑴]是比第k+1小的元素,那末B[k/2⑴]最少是第k+2大的元素。但是在A中最多有k/2⑴个元素小于A[k/2⑴],在B中最多有k/2⑴个元素小于A[k/2⑴],总共最多有(k/2⑴+k/2⑴)即k⑵个元素。所以A[k/2⑴]不可能大于第k个元素。所以我们可以删去,然后找第k-k/2=k/2个元素。
3、A[k/2⑴] > B[k/2⑴]
类似2
在这里要注意3种特殊情况
1、如果AB有1个是空,则返回非空数组下标为k⑴的元素,即A[k⑴]或B[k⑴]
2、如果k==1,则返回min{A[0],B[0]}
3、如果k/2比短的数组长的话(假定是A),则比较A[m⑴]和B[k/2⑴]
Ex:
A{1,3,7,8}     m1=4
B{2,4,5,6,7,8,9,10,12}   m2=9
由于删除元素较为麻烦,所以在程序中设两个变量begin1,begin2作为起始元素。再设置m1和m2作为有效数组长度。
1、合并后的数组,长度为m1+m2=13,那末我们要找出第13/2+1=7,即k=7,第7大的元素。刚开始begin1和begin2都为0,m1=4,m2=9
2、A[begin1+k/2⑴]=A[2]=7 > B[begin2+k/2⑴]=B[2]=5,所以我们删去B中的2,4,5,在程序中,我们可使begin2指针指向元素6,即begin2=3,m2=9⑶=6,现在我们要找出k⑶即第4大的元素
3、k=4,begin1=0,begin2=3,m1=4,m2=6,A[begin1+k/2⑴]=A[1]=3 < B[begin2+k/2⑴]=B[7],所以我们删去A中1,3,begin1=0+2=2,m1=4⑵=2,现在我们要找出k⑵,即第2大的元素
4、k=2,begin1=2,begin2=3,m1=2,m2=6,A[begin1+k/2⑴]=A[2]=7 > B[begin2+k/2⑴]=B[3]=6,所以我们删去B中6,begin2=3+1=4,m2=6⑴=5,现在我们要找出k⑴,即第1大的元素
5、k=1,begin1=2,begin2=4,m1=2,m2=5比较A[begin1]=A[2]=7,B[begin2]=B[4]=7,返回7,终究结果为7

Accepted Code:

算法1:
class Solution { public: vector<int> MergeSort(vector<int>& nums1, vector<int>& nums2) { vector<int> res; int i=0,j=0; while(i<nums1.size() && j<nums2.size()) { if(nums1[i]<=nums2[j]) { res.push_back(nums1[i]); i++; } else { res.push_back(nums2[j]); j++; } } while(i<nums1.size()) { res.push_back(nums1[i]); i++; } while(j<nums2.size()) { res.push_back(nums2[j]); j++; } return res; } double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { vector<int> temp=MergeSort(nums1,nums2); double res; int len=temp.size(); if(temp.size()%2==0) res=(double)(temp[len/2]+temp[(len/2)⑴])/2; else res=temp[len/2]; return res; } };


算法2:
class Solution { public: double find_kth(vector<int>& nums1,vector<int>& nums2,int m1,int m2,int k,int begin1,int begin2) { if(m1 > m2) return find_kth(nums2,nums1,m2,m1,k,begin2,begin1); if(m1 == 0) return nums2[k⑴]; if(k == 1) return nums1[begin1] < nums2[begin2]?nums1[begin1]:nums2[begin2]; int a=min(k/2,m1); //the ath element in A int b=k-a; //the bth element in B if(nums1[begin1+a⑴] < nums2[begin2+b⑴]) //compare the ath element in A and the bth element in B return find_kth(nums1,nums2,m1-a,m2,k-a,begin1+a,begin2); else return find_kth(nums1,nums2,m1,m2-b,k-b,begin1,begin2+b); } double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int m1=nums1.size(); int m2=nums2.size(); int k=(m1+m2)>>1; if((m1+m2)%2==1) return find_kth(nums1,nums2,m1,m2,k+1,0,0); else return (find_kth(nums1,nums2,m1,m2,k+1,0,0)+find_kth(nums1,nums2,m1,m2,k,0,0))/2; } };








生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生