LeetCode: Median of Two Sorted Arrays

There are two sorted arrays A and B 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))

class Solution {public:double findMedianSortedArrays(int A[], int m, int B[], int n) {if((m+n) % 2 == 0)return (helper(A, m, B, n, (m+n)/2) + helper(A, m, B, n, (m+n)/2 – 1)) / 2.0;elsereturn helper(A, m, B, n, (m+n)/2);}private:int helper(int A[], int m, int B[], int n, int k){if(m == 0){return B[k];}if(n == 0)return A[k];if(k == 0)return std::min(A[0], B[0]);if(m/2 + n/2 > k){if(A[m/2] >= B[n/2]){return helper(A, m/2, B, n, k);}else{return helper(A, m, B, n/2, k);}}else{if(A[m/2] >= B[n/2]){return helper(A, m, B+(n/2), (n+1)/2 – 1, k-(n+1 – (n+1)/2));}else{return helper(A + m/2, (m+1)/2 – 1, B, n, k-(m+1 – (m+1)/2));}}}};

Round 2:

class Solution {public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size()-1;int n = nums2.size()-1;int k = (m + n + 2)/2;if((m + n) % 2 == 0){return ((getMedian(0, m, 0, n, nums1, nums2, k) + getMedian(0, m, 0, n, nums1, nums2, k-1)) / 2.0f);}else{return getMedian(0, m, 0, n, nums1, nums2, k);}}private:double getMedian(int s1, int e1, int s2, int e2, vector<int> &nums1, vector<int> &nums2, int k){if(s1 > e1)return nums2[s2 + k];if(s2 > e2)return nums1[s1 + k];if(k == 0)return std::min(nums1[s1], nums2[s2]);int m = e1 – s1 + 1;int n = e2 – s2 + 1;if(k == m/2 + n/2 && nums1[s1 + m/2] == nums2[s2 + n/2]){return nums1[s1 + m/2];}if(m/2 + n/2 >= k){if(nums1[s1 + m/2] > nums2[s2 + n/2]){return getMedian(s1, s1 + m/2 – 1, s2, e2, nums1, nums2, k);}else{return getMedian(s1, e1, s2, s2 + n/2 – 1, nums1, nums2, k);}}else{if(nums1[s1 + m/2] > nums2[s2 + n/2]){return getMedian(s1, e1, s2 + n/2 + 1, e2, nums1, nums2, k – n/2 – 1);}else{return getMedian(s1 + m/2 + 1, e1, s2, e2, nums1, nums2, k – m/2 – 1);}}}};

有理想在的地方，地狱就是天堂

相关文章：

你感兴趣的文章：

标签云：