[LeetCode]Find Median in Two Sorted Array

题目链接

Generalize 的问题就是在两个 sorted 的 array 里找第k个大的数。我们假设 x <= k，我们取第一个 array 的第 x 个数，取第二个 array 的 第 k - x个数。如果：

• A[x] <= B[k - m] 那么 A 中前 x个数不可能是答案
• A[x] > B[k - m] 那么 B 中前 k - x个数不可能是答案

那么对于 x我们每次可以取 k / 2 和 A.length 中的较小值。当 k / 2 > A.length 时，我们会把A全部砍掉，但是这并不影响时间复杂度，因为当我们不需要考虑A时，直接return B的第k大的数就可以了。时间复杂度 O(log k) = O(log (m + n))，因为我们每次砍掉k的一半的数。代码如下：

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

view raw Median of Two Sorted Arrays.cpp hosted with ❤ by GitHub

第二种不好 generalize，每次我们砍掉较短的 array 的 (len - 1) / 2，的长度，对应的长的 array 我们也砍掉这么多，那么可以保证中位数还是砍掉后的两个 array 的中位数，这么一直做直到较短的 array 剩下 一个元素或者两个元素，即有两种base case，时间复杂度 O(log  min (m , n))。代码如下：

	public class Solution {
	private double min(double a, double b){
	return a >= b? b: a;
	}
	private double max(double a, double b){
	return a >= b? a: b;
	}
	private double findMedian(int[] A, int lo, int hi){
	int mid = (lo + hi) / 2;
	int len = hi - lo + 1;
	return len % 2 == 0? (A[mid] + A[mid + 1]) / 2.0: A[mid];
	}
	private double findMedianBaseCaseOne(int[] A, int lo, int hi, double med1){
	double med2 = findMedian(A, lo, hi);
	int len = hi - lo + 1;
	int mid = (lo + hi) / 2;
	if (len % 2 == 0){
	if (med1 > med2)
	return min(med1, A[mid + 1]);
	else if (med1 < med2)
	return max(med1, A[mid]);
	else
	return med1;
	}else {
	int a = mid - 1 < lo? Integer.MIN_VALUE: A[mid - 1];
	int b = A[mid];
	int c = mid + 1 > hi? Integer.MAX_VALUE: A[mid + 1];
	if (med1 > med2)
	return (b + min(med1, c)) / 2.0;
	else if (med1 < med2)
	return (b + max(med1, a)) / 2.0;
	else
	return med1;
	}
	}
	private double findMedianBaseCaseTwo(int[] A, int lo, int hi, int left, int right){
	double med2 = findMedian(A, lo, hi);
	int len = hi - lo + 1;
	int mid = (lo + hi) / 2;
	if (len % 2 == 0){
	int a = mid - 1 < lo? Integer.MIN_VALUE: A[mid - 1];
	int b = A[mid], c = A[mid + 1];
	int d = mid + 2 > hi? Integer.MAX_VALUE: A[mid + 2];
	if (right <= b)
	return (max(right, a) + b) / 2.0;
	else if (left <= b)
	return (min(right, c) + b) / 2.0;
	else if (left >= c)
	return (min(left, d) + c) / 2.0;
	else if (right >= c)
	return (left + c) / 2.0;
	else
	return (left + right) / 2.0;
	} else {
	int a = A[mid - 1];
	int b = A[mid];
	int c = A[mid + 1];
	if (left >= b)
	return min(c, left);
	else if (right <= b)
	return max(right, a);
	else
	return b;
	}
	}
	private double findMedianRecursion(int[] A, int lo1, int hi1, int[] B, int lo2, int hi2){
	int len1 = hi1 - lo1 + 1;
	int len2 = hi2 - lo2 + 1;
	double med1 = findMedian(A, lo1, hi1);
	double med2 = findMedian(B, lo2, hi2);
	if (len1 == 1)
	return findMedianBaseCaseOne(B, lo2, hi2, A[lo1]);
	if (len2 == 1)
	return findMedianBaseCaseOne(A, lo1, hi1, B[lo2]);
	if (len1 == 2)
	return findMedianBaseCaseTwo(B, lo2, hi2, A[lo1], A[hi1]);
	if (len2 == 2)
	return findMedianBaseCaseTwo(A, lo1, hi1, B[lo2], B[hi2]);
	int cutLen = len1 >= len2? len2: len1;
	cutLen = (cutLen - 1) / 2;
	if (med1 > med2)
	return findMedianRecursion(A, lo1, hi1 - cutLen, B, lo2 + cutLen, hi2);
	else if (med1 < med2)
	return findMedianRecursion(A, lo1 + cutLen, hi1, B, lo2, hi2 - cutLen);
	else
	return med1;
	}
	public double findMedianSortedArrays(int A[], int B[]) {
	int len1 = A.length;
	int len2 = B.length;
	if (len1 == 0 && len2 == 0)
	return 0;
	if (len1 == 0)
	return findMedian(B, 0 ,len2 - 1);
	if (len2 == 0)
	return findMedian(A, 0, len1 - 1);
	return findMedianRecursion(A, 0, len1 - 1, B, 0, len2 - 1);
	}
	}

view raw find median in two sorted array v-2.java hosted with ❤ by GitHub