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)).
这道题让我们求两个有序数组的中位数，而且限制了时间复杂度为O(log (m+n))，看到这个时间复杂度，自然而然的想到了应该使用二分查找法来求解。但是这道题被定义为Hard也是有其原因的，难就难在要在两个未合并的有序数组之间使用二分法，这里我们需要定义一个函数来找到第K个元素，由于两个数组长度之和的奇偶不确定，因此需要分情况来讨论，对于奇数的情况，直接找到最中间的数即可，偶数的话需要求最中间两个数的平均值。下面重点来看如何实现找到第K个元素，首先我们需要让数组1的长度小于或等于数组2的长度，那么我们只需判断如果数组1的长度大于数组2的长度的话，交换两个数组即可，然后我们要判断小的数组是否为空，为空的话，直接在另一个数组找第K个即可。还有一种情况是当K = 1时，表示我们要找第一个元素，只要比较两个数组的第一个元素，返回较小的那个即可。
C++ 解法一：
class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int total = nums1.size() + nums2.size(); if (total % 2 == 1) { return findKth(nums1, 0, nums2, 0, total / 2 + 1); } else { return (findKth(nums1, 0, nums2, 0, total / 2) + findKth(nums1, 0, nums2, 0, total / 2 + 1)) / 2; } } double findKth(vector<int> &nums1, int i, vector<int> &nums2, int j, int k) { if (nums1.size() - i > nums2.size() - j) return findKth(nums2, j, nums1, i, k); if (nums1.size() == i) return nums2[j + k - 1]; if (k == 1) return min(nums1[i], nums2[j]); int pa = min(i + k / 2, int(nums1.size())), pb = j + k - pa + i; if (nums1[pa - 1] < nums2[pb - 1]) return findKth(nums1, pa, nums2, j, k - pa + i); else if (nums1[pa - 1] > nums2[pb - 1]) return findKth(nums1, i, nums2, pb, k - pb + j); else return nums1[pa - 1]; } };
上面的方法变量太多，较为复杂，我们也可以通过在findKth函数改变数组元素的个数来去掉一些变量，使整体看起来更加简洁清楚，参见代码如下：
C++ 解法二：
class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int m = nums1.size(), n = nums2.size(); return (findKth(nums1, nums2, (m + n + 1) / 2) + findKth(nums1, nums2, (m + n + 2) / 2)) / 2.0; } int findKth(vector<int> nums1, vector<int> nums2, int k) { int m = nums1.size(), n = nums2.size(); if (m > n) return findKth(nums2, nums1, k); if (m == 0) return nums2[k - 1]; if (k == 1) return min(nums1[0], nums2[0]); int i = min(m, k / 2), j = min(n, k / 2); if (nums1[i - 1] > nums2[j - 1]) { return findKth(nums1, vector<int>(nums2.begin() + j, nums2.end()), k - j); } else { return findKth(vector<int>(nums1.begin() + i, nums1.end()), nums2, k - i); } return 0; } };
Java 解法二：
public class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length, n = nums2.length, left = (m + n + 1) / 2, right = (m + n + 2) / 2; return (findKth(nums1, nums2, left) + findKth(nums1, nums2, right)) / 2.0; } int findKth(int[] nums1, int[] nums2, int k) { int m = nums1.length, n = nums2.length; if (m > n) return findKth(nums2, nums1, k); if (m == 0) return nums2[k - 1]; if (k == 1) return Math.min(nums1[0], nums2[0]); int i = Math.min(m, k / 2), j = Math.min(n, k / 2); if (nums1[i - 1] > nums2[j - 1]) { return findKth(nums1, Arrays.copyOfRange(nums2, j, n), k - j); } else { return findKth(Arrays.copyOfRange(nums1, i, m), nums2, k - i); } } }
此题还能用二分搜索法来解，是一种相当巧妙的应用，讲解在这个帖子中写的十分清楚，等有时间我再来写写分析过程：
C++ 解法三：
class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int m = nums1.size(), n = nums2.size(); if (m < n) return findMedianSortedArrays(nums2, nums1); if (n == 0) return ((double)nums1[(m - 1) / 2] + (double)nums1[m / 2]) / 2.0; int left = 0, right = n * 2; while (left <= right) { int mid2 = (left + right) / 2; int mid1 = m + n - mid2; double L1 = mid1 == 0 ? INT_MIN : nums1[(mid1 - 1) / 2]; double L2 = mid2 == 0 ? INT_MIN : nums2[(mid2 - 1) / 2]; double R1 = mid1 == m * 2 ? INT_MAX : nums1[mid1 / 2]; double R2 = mid2 == n * 2 ? INT_MAX : nums2[mid2 / 2]; if (L1 > R2) left = mid2 + 1; else if (L2 > R1) right = mid2 - 1; else return (max(L1, L2) + min(R1, R2)) / 2; } return -1; } };
Java 解法三：
public class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length, n = nums2.length; if (m < n) return findMedianSortedArrays(nums2, nums1); if (n == 0) return (nums1[(m - 1) / 2] + nums1[m / 2]) / 2.0; int left = 0, right = 2 * n; while (left <= right) { int mid2 = (left + right) / 2; int mid1 = m + n - mid2; double L1 = mid1 == 0 ? Double.MIN_VALUE : nums1[(mid1 - 1) / 2]; double L2 = mid2 == 0 ? Double.MIN_VALUE : nums2[(mid2 - 1) / 2]; double R1 = mid1 == m * 2 ? Double.MAX_VALUE : nums1[mid1 / 2]; double R2 = mid2 == n * 2 ? Double.MAX_VALUE : nums2[mid2 / 2]; if (L1 > R2) left = mid2 + 1; else if (L2 > R1) right = mid2 - 1; else return (Math.max(L1, L2) + Math.min(R1, R2)) / 2; } return -1; } }
本文转自博客园Grandyang的博客，原文链接：两个有序数组的中位数[LeetCode] Median of Two Sorted Arrays ，如需转载请自行联系原博主。