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)).
Example 1:
nums1 = [1, 3] nums2 = [2] The median is 2.0
Example 2:
nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5
解法1: 将问题转化为经典的“求两个有序数组中的第k小值”问题，即：
首先假设有序数组A和B的长度都大于k/2（下取整），比较A[k/2-1]和B[k/2-1]两个元素，这两个元素分别表示A和B中的第k/2小的元素。这两个元素比较共有三种情况：>、<和=。
（1）如果A[k/2-1]<B[k/2-1]，说明A[k/2-1]及其之前的元素肯定都在A和B所有元素的前(k-1)小元素中，也就是说，A[k/2-1]不可能大于两个数组所有元素的第k小值。因此，将A的前(k/2)个元素删去之后（设剩余部分为A‘），进一步求A‘和B中的第(k-k/2)大的数。
（2）如果A[k/2-1]<B[k/2-1]，同理。
（3）如果A[k/2-1]=B[k/2-1]，如果k为偶数，则A[k/2-1]和B[k/2-1]即为第k小数，因为两个数组中分别有(k/2-1)个元素小于该值。但考虑到k可能不为偶数，可将其中一个的前(k/2)个元素删去之后，求剩余部分的第(k-k/2)大的数。
需要注意的是，如果A的长度m<k/2，应取A[m-1]与B[k/2-1]（或B[k-m-1]）比较；B的长度小于k/2时同理。
通过上面的分析，我们即可以采用递归的方式实现寻找第k小的数。此外我们还需要考虑几个边界条件：
public class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int len1 = nums1.length; int len2 = nums2.length; int left = (len1 + len2 + 1) / 2; int right = (len1 + len2 + 2) / 2; return (findKthSmallest(nums1, nums2, left) + findKthSmallest(nums1, nums2, right)) / 2.0; } // 将问题转化为求两个数组的第k小数 public int findKthSmallest(int[] nums1, int[] nums2, int k) { int len1 = nums1.length; int len2 = nums2.length; int half = k / 2; // 如果有其中一个长度为零，直接返回另一个的第k小数 if (len1 == 0) return nums2[k - 1]; if (len2 == 0) return nums1[k - 1]; // 如果k为1，则直接返回两个数组的最小数 if (k == 1) return Math.min(nums1[0], nums2[0]); // 判断half是否超过了数组长度 int cutPoint1 = Math.min(len1, half); int cutPoint2 = Math.min(len2, half); // 判断两个数组切割点处的值大小，将小的数组从切割点处截去 if (nums1[cutPoint1 - 1] < nums2[cutPoint2 - 1]) { return findKthSmallest(Arrays.copyOfRange(nums1, cutPoint1, len1), nums2, k - cutPoint1); } else { return findKthSmallest(nums1, Arrays.copyOfRange(nums2, cutPoint2, len2), k - cutPoint2); } } }
解法2:
－－－－－－－－－－－－－－－－－－－－ 准备工作 －－－－－－－－－－－－－－－－－－－－
对于长为N的数组A来说，用L和R分别表示中位数切割点的值（N为奇数）或者左右两侧的值（N为偶数），则L=(N-1)/2, R=N/2, 所以中位数可以表示为: (L+R) / 2 = (A[(N-1)/2] + A[N/2]) / 2。
在数组的每两个数字之间添加“虚拟位置”（用#表示），同时把数字也当成“位置”，如：
[6 9 13 18] -> [# 6 # 9 # 13 # 18 #] (N = 4) position index 0 1 2 3 4 5 6 7 8 (N_Position = 9) [6 9 11 13 18]-> [# 6 # 9 # 11 # 13 # 18 #] (N = 5) position index 0 1 2 3 4 5 6 7 8 9 10 (N_Position = 11)
可以看出，对于长度为N的数组，总共有(2*N+1)个位置，无论N为奇数还是偶数，而中位数切割点的位置也总是第N个（下标从0开始）。
－－－－－－－－－－－－－－－－－－－－ 算法原理 －－－－－－－－－－－－－－－－－－－－
设有序数组A1和A2，A1的长度>A2的长度：
A1: [# 1 # 2 # 3 # 4 # 5 #] (N1 = 5, N1_positions = 11)
pos: 0 1 2 3 4 5 6 7 8 9 10 A2: [# 1 # 1 # 1 # 1 #] (N2 = 4, N2_positions = 9)
pos: 0 1 2 3 4 5 6 7 8
与一个数组的中位数问题一样，我们需要对两个数组进行切割，使得左侧的所有数字 < 右侧的所有数字。
可以注意到：
[# 1 # 2 # 3 # (4/4) # 5 #] [# 1 / 1 # 1 # 1 #]
L1 = A1[(C1-1)/2]; R1 = A1[C1/2]; L2 = A2[(C2-1)/2]; R2 = A2[C2/2];
在上述例子中，
L1 = A1[(7-1)/2] = A1[3] = 4; R1 = A1[7/2] = A1[3] = 4;
L2 = A2[(2-1)/2] = A2[0] = 1; R2 = A1[2/2] = A1[1] = 1;
现在如何确定切割点是不是我们想要的？由于L1和L2是左侧的两个最大值，而R1和R2是右侧的两个最小值，我们只需满足：
L1 <= R1 && L1 <= R2 && L2 <= R1 && L2 <= R2
从而保证左侧的数字 <= 右侧的数字。由于A1和A2是有序的，即满足L1 <= R1 和 L2 <= R2，因此只需满足
L1 <= R2 和 L2 <= R1即可。
现在我们可以应用二分法进行查找：
需要注意的是：
public class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length; int 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; int right = 2 * n; while (left <= right) { int mid2 = (left + right) / 2; int mid1 = m + n - mid2; int L1 = mid1 == 0 ? Integer.MIN_VALUE : nums1[(mid1 - 1) / 2]; int R1 = mid1 == m * 2 ? Integer.MAX_VALUE : nums1[mid1 / 2]; int L2 = mid2 == 0 ? Integer.MIN_VALUE : nums2[(mid2 - 1) / 2]; int R2 = mid2 == n * 2 ? Integer.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.0; } return -1; } }
[LeetCode] 4. Median of Two Sorted Arrays ☆☆☆☆☆
原文：http://www.cnblogs.com/strugglion/p/6387677.html