概念
在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
原题
4. Median of Two Sorted Arrays （Hard)
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.
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
4. 两个有序数组的中位数 (困难）
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
- 本题在LeetCode上在分而治之分类下
题意分析
根据题目要求，两个有序数组寻找中位数，自然可以联想到最简单的有序数组合并。但是合并有序数组寻找中位数显然算法复杂度会超过题目要求的O(log(m + n)),不过根据题目的复杂度要求O(log(m + n))又能明显的想到题解思路必然跟分而治之算法思想相关，因为只有分治法思想的算法复杂度才能达到log级别。
思路设计
由于本题是求中位数，题解必然属于分治，可采用二分法。若要找出两个数组所有数中的第k个数，可以采用淘汰法，每次取两个数组中的前k/2个数，比较两个数组中第k/2个数得出较小的那一个，可以淘汰掉较小数所在数组的k/2之前的所有数，接着得到两个新数组递归循环淘汰
最后直到累计找到第k个数。
举例说明，假设有两个数组m、n长度分别为5、10。由于是寻找中位数，因此数组之和len=5+10=15为奇数，中位数正好是第8个数即k为8。
1、k = 8, k/2 = 4，淘汰4位;
image
第一次将A和B分别取前k/2 = 4个数，如上图所示，由于B数组中第4位数4小于A数组中第4位数11，因此淘汰B数组的前4位，同时得出新数组继续比较。由于此时总数已经舍弃4个得出新k为8-4=4。
2、k = 4，k/2 = 2，再淘汰2位;
image
第二次将A和B分别取前k/2 = 2个数，如上图所示，由于A数组中第2位数4小于B数组中第2位数6，因此淘汰A数组的前2位，同时得出新数组继续比较。由于此时总数已经舍弃2个得出新k为4-2=2。
3、k= 2, k/2 = 1，再淘汰1位;
image
第三次将A和B分别取前k/2 = 1个数，如上图所示，由于A数组中第1位数5等于B数组中第1位数5，因此仍淘汰A数组的前1位，此时k为1结束二分，并且此时总数已经舍弃1个得出新k位2-1=1。
4、k=1时，到达第8位，结束循环
image
最后一次因为寻找的数字为第8位，故只需对比新数组A、B的第一位得出较小的数即可。由于数组B第1位数5小于数组A第1位数，因此5便是最终两个数组的中位数。
特殊情况
- 若数组和为偶数，则必然有两个中位数，分别是第k个数和第k+1个数（k和k+1位表示在总数组中的相对顺序）。
- 若A、B数组中若较短的数组A长度小于k/2时,为避免数组越界，直接淘汰A数组,下一轮新的k的值则变成k-A.length。
伪代码
一、求两数组中位数（findMedianSortedArrays方法）
1、根据nums1数组长度len1和nums2数组长度len2得到中位数k；
2、i.若两数组总长为奇数，此时只有一个中位整数，直接调用方法二返回两数组的第k位数；
ii.若两数组总长为偶数，此时有两个中位整数，分别是第k和第k+1位，调用方法二传入k、k+1计算2个中位整数平均值得出中位数；
二、根据数组，起始位置，k值，求两有序数组的第k位整数（numberK方法）
1、根据两数组的起始位置和长度得出当前数组的有效长度len1、len2；
2、保证有效长度小的数组在前面；
3、特殊情况处理，当len1为0即第一个有效数组为空时，直接返回第2个数组的第k位整数（相对起始位置）；
4、特殊情况处理，当两数组均只有1个元素时直接返回较小的的整数；
5、根据起始位置、数组长度、k值分别计算两个数组相对起始位置的第k个数的下标。注意当数组长度小于k时，特殊处理将下标移到数组最后一位；
6、对比两数组第k个数的大小：
i.若第2个数组的第k个数较小，则移动第2个数组指针，相对于起始位置k位，相当于淘汰第2个数组的k个数，继续递归调用；
ii.反之若第1个数组的第k个数较小，则移动第1个数指针，相对于起始位置k位，相当于淘汰第1个数组的k个数，继续递归调用；
编码实践
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int k = (len1 + len2 + 1) / 2;
if (((len1 + len2) & 1) == 1) {
return numberK(nums1, 0, nums2, 0, k);
} else {
return (numberK(nums1, 0, nums2, 0, k) + numberK(nums1, 0, nums2, 0, k + 1)) * 0.5;
}
}
private int numberK(int[] n1, int start1, int[] n2, int start2, int k) {
int len1 = n1.length - start1;
int len2 = n2.length - start2;
if (len1 > len2) {
return numberK(n2, start2, n1, start1, k);
}
if (len1 == 0) {
return n2[start2 + k - 1];
}
if (k == 1) {
return Math.min(n1[start1], n2[start2]);
}
int end1 = start1 + Math.min(len1, k / 2) - 1;
int end2 = start2 + Math.min(len2, k / 2) - 1;
if (n1[end1] > n2[end2]) {
return numberK(n1, start1, n2, end2 + 1, k - (end2 - start2 + 1));
} else {
return numberK(n1, end1 + 1, n2, start2, k - (end1 - start1 + 1));
}
}
image
结语
本题属于分而治之思想的经典，分治法思想中的二分法类型，在leetcode上属于困难题型，主要考察分治法设计以及算法复杂度的优化。最后，如果觉得本文对你有所帮助或启发那就来个赞吧0.0～～
关注订阅号 获取更多干货～
网友评论