Description:
https://leetcode.com/problems/median-of-two-sorted-arrays/#/description
Boundary & Algorithm:
Should separate odd and even.
Use recursion, so boundary includes:
- destination pos = 0: return directly
- destination pos = 1 : return min{A[0], B[0]}
Code:
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
int total = m + n;
if (total & 0x1)
return find_kth(nums1, m, nums2, n, total / 2 + 1);
else
return (find_kth(nums1, m, nums2, n, total / 2)
+ find_kth(nums1, m, nums2, n, total / 2 + 1)) / 2;
}
private:
static double find_kth(vector<int> A, int m, vector<int> B, int n, int k) {
//always assume that m is equal or smaller than n
if (m > n) return find_kth(B, n, A, m, k);
if (m == 0) return B[k – 1];
if (k == 1) return min(A[0], B[0]);
//divide k into two parts
int pa = min(k / 2, m), pb = k – pa;
if (A[pa – 1] < B[pb – 1])
{
A.erase(A.begin(), A.begin() + pa);
return find_kth(A, m – pa, B, n, k – pa);
}
else if (A[pa – 1] > B[pb – 1])
{
B.erase(B.begin(), B.begin() + pb);
return find_kth(A, m, B, n – pb, k – pb);
}
else
return A[pa – 1];
}
};