问题描述：
给定两个大小为 m 和 n 的有序数组nums1 和nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
示例 1:
nums1 = [1, 3]
nums2 = [2]
中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
中位数是 (2 + 3)/2 = 2.5
看到问题我的第一反应就是 融合两个数组再排序， 两数组的合并长度的奇偶来判断具体的位置获取中位数。
然后就是有了下面的写法1，哈哈（好吧，我承认自己是有点垃圾）：
public static final int[] nums1 = {1,4,7,10,15};
public static final int[] nums2 = {3,4,5,11,18};
public static void main(String[] args) {
solutionOne(nums1, nums2);
}
public static void solutionOne(int[] nums1, int[] nums2) {
// 建立第三个融合数组
int nums3[] = Arrays.copyOf(nums1, nums1.length + nums2.length);
System.arraycopy(nums2, 0, nums3, nums1.length, nums2.length);
// 对数组进行排序
Arrays.sort(nums3);
int arrayLen = nums3.length;
if (arrayLen % 2 == 0) {
int centerLen = arrayLen / 2;
System.err.print((double)((nums3[centerLen - 1] + nums3[centerLen]) / 2));
} else {
System.out.println(nums3[arrayLen / 2]);
}
}
然后如果是要求算法的时间复杂度为 O(log (m+n)) 就不能这样了， 跑去查了下
思路：
其实想下结果就知道最后的中位数 一定是在大于一半数组 和 小于一半数组的中间的，所以用二分法。
用二分法拆分两个数组nums1, nums2，保证每一次拆分的都是去掉两个数组的一半子数组的。
相对来说 短数组肯定是相对于长数组更早轮训完。
算法的复杂度为 O(log (m+n)) ，m 为数组A长度， n 为数组B长度。中位数的位置应该是 k = ( m + n ) / 2 +1
从两个数组整体来看，当长度 L= m + n 是偶数时，要求第 (L / 2) 和第 (L / 2 + 1) 的两个数取均值。
我们可以砍掉一部分，假设砍掉的部分长度为 length，那么接下来就是在剩下的数组里求第 (k - length) 的数。
逐层缩小范围，直到两数组其中一个走完，或者要求的是第 1 大的元素，就可以直接返回结果了。
要找融合数组 C 的第 k 元素，即 C[k-1]，那如果我们从 A 和 B 中分别取前 k/2 个元素，其中必然有一部分是
在数组 C 的前 k 个数里。设 mid = k / 2，当比较两数组第 k / 2位置数值 A[mid - 1] < B[mid - 1] 时，可以断定
A 的前 mid 个元素是在 C 的前 k 个数里，那么我们则舍弃 A 的前 mid 个元素。反之则舍弃 B 的前 mid 个元素。
现在数组 A 或者 B 已经舍弃掉 k/2 个元素，缩小查找范围了，不断递归选择下去，直到找到目标元素！
public static double solutionThrid(int[] A, int[] B) {
int len = A.length + B.length;
if(len % 2 != 0 ) {
return findKit(A, 0, B, 0 ,(len/2)+1);
}
return (findKit(A, 0, B, 0, len/2) + findKit(A, 0, B, 0, len/2+1))/2;
}
public static int findKit(int[] A, int siteA, int[] B, int siteB, int k) {
// 如果A数组的轮训位置到了A的长度，那么B数组剩下的中位数就是结果
if(siteA >= A.length) {
return B[siteB+k-1];
}
// 如果B数组的轮训位置到了B的长度，那么A数组剩下的中位数就是结果
if(siteB >= B.length) {
return A[siteA+k-1];
}
// 如果轮训到最后取小的值
if(k==1) {
return Math.min(A[siteA], B[siteB]);
}
// 取下次的AB轮训位置
int nextSiteA = siteA + k/2 -1 < A.length?A[siteA+k/2-1]:Integer.MAX_VALUE;
int nextSiteB = siteB + k/2 -1 < B.length?B[siteB+k/2-1]:Integer.MAX_VALUE;
if(nextSiteA < nextSiteB) {
return findKit(A, siteA+k/2, B, siteB, k-k/2);
}else {
return findKit(A, siteA, B, siteB+k/2, k-k/2);
}
}
官方解答：
class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
if (m > n) { // to ensure m<=n
int[] temp = A; A = B; B = temp;
int tmp = m; m = n; n = tmp;
}
int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = halfLen - i;
if (i < iMax && B[j-1] > A[i]){
iMin = iMin + 1; // i is too small
}
else if (i > iMin && A[i-1] > B[j]) {
iMax = iMax - 1; // i is too big
}
else { // i is perfect
int maxLeft = 0;
if (i == 0) { maxLeft = B[j-1]; }
else if (j == 0) { maxLeft = A[i-1]; }
else { maxLeft = Math.max(A[i-1], B[j-1]); }
if ( (m + n) % 2 == 1 ) { return maxLeft; }
int minRight = 0;
if (i == m) { minRight = B[j]; }
else if (j == n) { minRight = A[i]; }
else { minRight = Math.min(B[j], A[i]); }
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
}
题目： https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/
网友评论