spider68

Median of Two Sorted Arrays

Jul 22nd, 2021
1,042
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.    
  4.     int kthElement(vector<int>& arr1, vector<int>& arr2, int k){
  5.         int n= arr1.size();
  6.         int m= arr2.size();
  7.        
  8.         int l = min(arr1[0] , arr2[0]) ;
  9.         int r = max(arr1[n - 1] , arr2[m - 1]);
  10.         int ans=arr1[0];
  11.         while(l <= r)
  12.         {
  13.             int mid = (l + r ) / 2;
  14.             int x = upper_bound(arr1.begin(), arr1.end() , mid) - arr1.begin() ;
  15.             int y = upper_bound(arr2.begin(), arr2.end() , mid) - arr2.begin() ;
  16.            
  17.             if(x + y < k )l = mid + 1 ;
  18.             else{
  19.                 ans=mid;
  20.                 r = mid - 1 ;
  21.             }
  22.         }
  23.         return ans ;
  24.     }
  25.     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
  26.         int n=nums1.size(),m=nums2.size();
  27.         if(n>m)return findMedianSortedArrays(nums2,nums1);
  28.         if(m==0)return 0.0;
  29.         if(n==0){
  30.             int mid=m/2;
  31.            
  32.             if(m%2==1){
  33.                 return nums2[mid];
  34.             }    
  35.             return (nums2[mid]+nums2[mid-1])/2.0;
  36.         }
  37.         if((m+n)%2)return kthElement(nums1,nums2,(m+n+1)/2);
  38.         else{
  39.             int x=kthElement(nums1,nums2,(m+n)/2);
  40.             int y=kthElement(nums1,nums2,(m+n)/2+1);
  41.             return (x+y)/2.0;
  42.         }
  43.     }
  44. };
RAW Paste Data