博文中会简要介绍Leetcode P0004题目分析及解题思路。
“Median of Two Sorted Arrays”其实一道General的难题的一个特例，原本的题目是在两个数组里寻找第k个数。这篇博文将直接介绍通用的解法。
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.
题干对复杂度的要求是O(log(m+n))，而一般来说这样的复杂度要求暗示了解法需要采取二分的思路，而一般来说二分法中分而治之的思路又会导向递归解法。所以总的来说，此题会涉及基于递归的二分法。
基于递归的二分法的思想在面试中十分常见。一般的思路是“排除一半，保留一半，递归之”。本题也是类似的思路，唯一需要关注的是排除对象主体是什么，是两个数组中的所有数据还是k个数据。如果此时过分关注Median反而会陷入困境，将两个数组中的所有数据当成排除的主体对象。如果是这样，思路会变得复杂，代码难度也会随之提高。
此时需要想到的便是这道题的General版本，即寻找第k个数，此时的第k个数则恰好是中位数。通过思考其General版本，我们更容易得出排除的主体对象其实是k个数据而不是所有数据，因为对于第k个数而言，排除所有数据的一半并不能带来直接效益，反而是排除k/2个数据对寻找第k个数更有帮助。
于是，我们获得了更加简单明了的思路，即每次在两个数组中排除k/2个一定不会包含第k个数的数据，然后下次则考量k-k/2个数，排除其1/2，依次类推，递归之。
以下是Java的题解代码实现。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length, len2 = nums2.length;
// 简化对总数是奇偶的判断。奇，则leftMed=rightMed；偶，则leftMed=rightMed-1。
int leftMed = (len1 + len2 + 1) / 2, rightMed = (len1 + len2 + 2) / 2;
if (nums1.length == 0)
return (nums2[leftMed-1] + nums2[rightMed-1]) / 2.0;
if (nums2.length == 0)
return (nums1[leftMed-1] + nums1[rightMed-1]) / 2.0;
return (this.findKth(nums1, 0, nums2, 0, leftMed) + this.findKth(nums1, 0, nums2, 0, rightMed)) / 2.0;
}
private double findKth(int[] nums1, int i1, int nums2[], int j2, int k) {
// 边界条件是，如果数组nums1中所有数都被排除了，则第k个数一定在数组nums2中，只需要将坐标向右移动k-1即可以包含k个数，用掉所有剩余的k。
if (i1 >= nums1.length)
return nums2[j2+k-1];
if (j2 >= nums2.length)
return nums1[i1+k-1];
if (k == 1)
return Math.min(nums1[i1], nums2[j2]);
// 核心思路：每次判断k/2个数，若val1>val2，则可以得出数组nums2中k/2个数一定不包含第k个数，反之亦然。对于边界，可以用MAX_VALUE巧妙解决。
int val1 = (i1+k/2-1 < nums1.length)? nums1[i1+k/2-1]: Integer.MAX_VALUE;
int val2 = (j2+k/2-1 < nums2.length)? nums2[j2+k/2-1]: Integer.MAX_VALUE;
if (val1 > val2)
return this.findKth(nums1, i1, nums2, j2+k/2, k-k/2);
else
return this.findKth(nums1, i1+k/2, nums2, j2, k-k/2);
}
}
以下是C++的题解代码实现。
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size(), len2 = nums2.size();
int left_med = (len1 + len2 + 1) / 2, right_med = (len1 + len2 + 2) / 2;
if (len1 == 0)
return (nums2[left_med-1] + nums2[right_med-1]) / 2.0;
if (len2 == 0)
return (nums1[left_med-1] + nums1[right_med-1]) / 2.0;
return (find_kth(nums1, 0, nums2, 0, left_med) + find_kth(nums1, 0, nums2, 0, right_med)) / 2.0;
}
double find_kth(const vector<int>& nums1, int i1, const vector<int>& nums2, int j2, int k) {
if (i1 >= nums1.size())
return nums2[j2+k-1];
if (j2 >= nums2.size())
return nums1[i1+k-1];
if (k == 1)
return min(nums1[i1], nums2[j2]);
int val1 = i1+k/2-1 >= nums1.size()? INT_MAX: nums1[i1+k/2-1];
int val2 = j2+k/2-1 >= nums2.size()? INT_MAX: nums2[j2+k/2-1];
if (val1 > val2)
return find_kth(nums1, i1, nums2, j2+k/2, k-k/2);
else
return find_kth(nums1, i1+k/2, nums2, j2, k-k/2);
}
};