# LeetCode Median of Two Sorted Arrays

LeetCode Median of Two Sorted Arrays
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)).

int findKthSmallest(int A[], int m, int B[], int n, int k) {
assert(m >= 0); assert(n >= 0); assert(k > 0); assert(k <= m+n);

int i = (int)((double)m / (m+n) * (k-1));
int j = (k-1) - i;

assert(i >= 0); assert(j >= 0); assert(i <= m); assert(j <= n);
// invariant: i + j = k-1
// Note: A[-1] = -INF and A[m] = +INF to maintain invariant
int Ai_1 = ((i == 0) ? INT_MIN : A[i-1]);
int Bj_1 = ((j == 0) ? INT_MIN : B[j-1]);
int Ai   = ((i == m) ? INT_MAX : A[i]);
int Bj   = ((j == n) ? INT_MAX : B[j]);

if (Bj_1 < Ai && Ai < Bj)
return Ai;
else if (Ai_1 < Bj && Bj < Ai)
return Bj;

assert((Ai > Bj && Ai_1 > Bj) ||
(Ai < Bj && Ai < Bj_1));

// if none of the cases above, then it is either:
if (Ai < Bj)
// exclude Ai and below portion
// exclude Bj and above portion
return findKthSmallest(A+i+1, m-i-1, B, j, k-i-1);
else /* Bj < Ai */
// exclude Ai and above portion
// exclude Bj and below portion
return findKthSmallest(A, i, B+j+1, n-j-1, k-j-1);
}


class Solution {
public:
double findKthSmallest(vector<int>& nums1, vector<int>& nums2, int k)//find kth smallest
{
int m = nums1.size(), n = nums2.size();
//always assume that m is equal or smaller than n
if (m > n)
return findKthSmallest(nums2, nums1, k);
if (m == 0)
return nums2[k - 1];
if (k == 1)
return min(nums1[0], nums2[0]);
//divide k into two parts
int i = (int)((double)m / (m + n)*(k - 1));
int j = (k - 1) - i;
int Ai_1 = ((i == 0) ? INT_MIN : nums1[i - 1]);
int Bj_1 = ((j == 0) ? INT_MIN : nums2[j - 1]);
int Ai = ((i == m) ? INT_MAX : nums1[i]);
int Bj = ((j == n) ? INT_MAX : nums2[j]);
if (Bj_1 < Ai && Ai < Bj)
return Ai;
else if (Ai_1 < Bj && Bj < Ai)
return Bj;
if (Ai < Bj)
{
vector<int> v1(nums1.begin() + i + 1, nums1.end());
vector<int> v2(nums2.begin(), nums2.begin() + j);
return findKthSmallest(v1, v2, k - i - 1);
}
else if (Ai > Bj)
{
vector<int> v1(nums1.begin(), nums1.begin() + i);
vector<int> v2(nums2.begin() + j + 1, nums2.end());
return findKthSmallest(v1, v2, k - j - 1);
}
else
return Ai;
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int total = nums1.size() + nums2.size();
if (total & 0x01)
return findKthSmallest(nums1, nums2, total / 2 + 1);
else
return (findKthSmallest(nums1, nums2, total / 2) + findKthSmallest(nums1, nums2, total / 2 + 1)) / 2;
}
};


O(lgn+lgm)的解法。假设arr1和arr2的中位数分别是arr1[mid1]和arr2[mid2]，如果mid1+mid2arr2[mid2]的情况类似。

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