LeetCode [4] Median of Two Sorted Arrays

4. Median of Two Sorted Arrays

Hard

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)).

You may assume nums1 and nums2 cannot be both empty.

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

 O（log（m + n））

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int m = nums1.size(), n = nums2.size(); if((m+n)%2==1){ return findKth(nums1.begin(), nums2.begin(), m, n, (m+n)/2+1); }else{ int x = findKth(nums1.begin(), nums2.begin(), m, n, (m+n)/2); int y = findKth(nums1.begin(), nums2.begin(), m, n, (m+n)/2+1); return (x+y)/2.0; } } int findKth(vector<int>::iterator it1, vector<int>::iterator it2, int m, int n, int k){ if(m>n) return findKth(it2, it1, n, m, k); if(m==0) return *(it2+k-1); if(k==1) return min(*it1, *it2); int a = min(m, k/2); int b = k-a; if(*(it1+a-1)>*(it2+b-1)){ return findKth(it1, it2+b, m, n-b, k-b); }else{ return findKth(it1+a, it2, m-a, n, k-a); } } };