Leetcode 4. Median of Two Sorted Arrays

佚名 6年前 (2019-04-24) 随笔 950人围观抢沙发百度已收录

https://leetcode.com/problems/median-of-two-sorted-arrays/

 1 class Solution {
 2 public:
 3     #include<algorithm>
 4     int get_kth_val(vector<int>& nums1, vector<int>& nums2,int l1,int l2,int k){
 5         
 6         int L1=nums1.size()-l1,L2=nums2.size()-l2;
 7         if(L1>L2) return get_kth_val(nums2,nums1,l2,l1,k);
 8         if(L1==0) return nums2[l2+k-1];
 9         if(k==1) return min(nums1[l1],nums2[l2]);
10         int ka=min(L1,k/2);
11         int kb=k-ka;
12         if(nums1[l1+ka-1] == nums2[l2+kb-1]) return nums1[l1+ka-1];
13         if(nums1[l1+ka-1] >  nums2[l2+kb-1]) return get_kth_val(nums1,nums2,l1,l2+kb,k-kb);
14         else return get_kth_val(nums1,nums2,l1+ka,l2,k-ka);
15     }
16     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
17         int L1=nums1.size(),L2=nums2.size();
18         /*
19         5->第3个和第3个
20         6->第3个和第4个
21         找到第(L1+L2+2)/2个和第(L1+L2+1)/2个
22         
23         查找第k个元素:
24         条件:A,B,B为长数组
25         ka=min(Len(A),k/2),kb=k-ka
26         若A[ka]==B[kb],则A[ka]为所求值
27         若A[ka] >B[kb],说明比B[kb]小的个数一定小于kb-1+ka-1,
28             即B[0...kb]是可以舍去的,进而求B[kb+1,...],A[0,...]的第k-kb个值
29         若A[ka]<B[kb],同理，A[0...ka]是可以舍去的,求A[ka+1...],B[0,...]的第k-ka个值
30         
31         每次至少舍去一半的k,或者整个A数组，若舍去整个数组，下一轮直接在B中索引第k-Len(A)个即可
32         
33         */
34         int a,b;
35         if((L1+L2) % 2) a = b = get_kth_val(nums1,nums2,0,0,(L1+L2+2)/2);
36         else a= get_kth_val(nums1,nums2,0,0,(L1+L2+2)/2),b=get_kth_val(nums1,nums2,0,0,(L1+L2+1)/2);
37         return (a+b)/2.0;
38     }
39 };