“你走过的路，只是别人走过的路。
image
相信看了这个标题的同学，对这道题以已经非常不陌生了，就是leecode当中的第四题，之所以要单独的写一写主要对我来说，里面涉及到比较重要的知识点：二分法，同时也提供了几道简单的练习题（后面也会遇到），就比较容易懂了。这道题也曾被Apple, Micosoft, Amazon, Zenefits, Yahoo, Dropbox, Adobe作为经典面试题。
题目
给定两个大小为 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
简单说一下要求时间复杂度为O(log(m + n)),就是想让我们利用二分法来解答，这里简单说一下二分法：
比如123456789，你要找2，首先查中间元素5，大于2，所以直接排除掉5右边的6789，然后在1234里继续二分查找。每次排除1/2的元素，所以是O(log2n)。简单推导一下：
推导
总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。 由于n/2k取整后>=1（最坏的情况是二分到只剩下一个），即令n/2k=1-> 2^K = n，可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn)。
热身一下，做几个简单练习题
①二分法练习1：寻找一个数
说白了，就是在一个有序数组中，给出一个目标数，二分找到这个数。
参考代码
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 注意
while(left <= right) {
int mid = left + (right - left) / 2; // 3 1
if(nums[mid] == target) // 是否是中间
return mid;
else if (nums[mid] < target) // 去掉了中间，肯定就在两边，如果中间<target 就在右边，从右边开始
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
}
return -1;
}
@Test
public void isbinarySearch() {
int[] nums = {1,2,2,2,3};
int i = binarySearch(nums,4);
Assert.assertNotNull(i);
}); }
image
②二分法练习2：寻找左侧边界的二分搜索
简单的说，找到了目标值，如果有多个目标值，取最左边的一个值。
参考代码
int left_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length; // 注意
while (left < right) { // 注意
int mid = left + (right - left) / 2; // 3 1
if (nums[mid] == target) { // 找左边就缩小右边
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid; // 注意
}
}
return left;
}
@Test
public void isleft_bound() {
int[] nums = {1, 2, 2, 2, 3};
int i = left_bound(nums, 2);
Assert.assertNotNull(i);
}
简单分析一下，相对前面那道题，这道题提高了一点难度
-
因为要找到最左侧的目标值，时间复杂度为logn,它的循环条件是left < right,如果相等的话会超出时间限制。
-
找到目标值，现在不能直接返回，需要找到最左侧的目标值，可以缩小右侧，令right = mid, 这里不能是right = mid -1，因为这个时候本来target = mid,如果right就是最左侧的目标值可能就会有问题了。
回到本题
做的这两道的训练题，对理解这道题很有帮助的。
求中位数，需要判断总长度的奇数偶数，如果是奇数直接取中位数，如果是偶数取中间两个数/2为中位数。
根据事例提出两个问题：
①是否能将两个数组二分为一个数组
②如果有些情况不能二分为一个数组（比如一个数组只有一个数但是数很大），当对两个数组之和二分至1的时候，排出了较小数之后，取两数组的最小值为中 位数。
image
针对第一个问题，事例1：
A: 1 2
B: 1 2 3 4 5 6 7 8 9 10
我们定义两个数组的索引，当A数组的索引index1等于A数组的length1,直接取B数组的索引+k(二分的mid) -1。
如果让index1=length1,说明A数组的所有值都作为较小值给排除掉了。
首先我们知道k=(length1+length2) + 1=7这是总长度的mid，我们对需要每个数组的mid然后比较排除较小的，所以k = k/2=3，我们知道A的长度是2，这里如果取A数组长度为3的值就会越界，所以我们取length1就行，
比较大小排除较小值，获取A数组的length1的值为2,获取B数组长度为3的值是3，因为2<3,直接排除A数组1~length的长度：令index1 = length，接下来计算k：
这里我们A数组长度为3越界了：k = k -length - index1 -1，如果没有越界就是k = k -k/2.
image
int index1 = 0, index2 = 0; // 初始化索引
if (index1 == length1) {
return nums2[index2 + k - 1]; // 因为是计算的length，所以对应数组下标进行-1
}
事例2:
A: 1 2 3 4 5 6 7 8 9 10
B: 1 2
相反，这里我直接给出结论。我们定义两个数组的索引，当B数组的索引index2等于B数组的length2,直接取A数组的索引+k(二分的mid) -1。
image
if (index2 == length2) {
return nums1[index1 + k - 1];
}
事例3：
A: 100 200
B: 1 2 3 4 5 6 7 8 9
对于这样的数组，我们是不能直接合成一个数组的，但是我们可以通过不断的二分，排除较小值，当k=1时，剩下的谁最小谁就是中位数。
简单分析一下，一共11个数，第6个数为mid,对mid除以2，得到half=3,长度为3的A数组越界，取length1=200>3,排除掉B数组的1, 2, 3 三个数，更新k=k-k/2 =6-3=3,index2=3
image
继续获取half = k/2=1,对A数组length=1的值为100，B数组对应的length=index2+half=4的值为4，因为100>4, 排除掉B数组的4,更新k=k-k/2=3-1=2,index2=4
image
继续获取half=1,对A数组length=1的值为100，B数组对应的length=index2+half=5的值为5，因为100>5, 排除掉B数组的5,更新k=k-k/2=2-1=1,index2=5
image
当k=1时，获取A[1]=100,B[5]=6,因为100>6,所以6就是我们的中位数。
if (k == 1) {
return Math.min(nums1[index1], nums2[index2]);
}
事例4：
A: 1 2 3 4 5 6 7 8 9
B: 1 2 3 4 5 6 7 8 9
本事例可按照事例3分析，留着看官分析吧。
参考代码
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int length1 = nums1.length, length2 = nums2.length;
int totalLength = length1 + length2;
if (totalLength % 2 == 1) { // 奇数
int midIndex = totalLength / 2;
double median = getKthElement(nums1, nums2, midIndex + 1);
return median;
} else {//
int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
return median;
}
}
public int getKthElement(int[] nums1, int[] nums2, int k) {
int length1 = nums1.length, length2 = nums2.length;
int index1 = 0, index2 = 0; // 初始化索引
int kthElement = 0;
while (true) {
// 边界情况
if (index1 == length1) {
return nums2[index2 + k - 1]; // 因为是计算的length，所以对应数组下标进行-1
}
if (index2 == length2) {
return nums1[index1 + k - 1];
}
if (k == 1) {
return Math.min(nums1[index1], nums2[index2]);
}
// 正常情况
int half = k / 2;
int newIndex1 = Math.min(index1 + half, length1) - 1;// k/2 - 1
int newIndex2 = Math.min(index2 + half, length2) - 1;
int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2]; // 比较 k/2 - 1
if (pivot1 <= pivot2) {
k -= (newIndex1 - index1 + 1); // k = k - k/2
index1 = newIndex1 + 1;//
} else {
k -= (newIndex2 - index2 + 1); // k = k - k/2
index2 = newIndex2 + 1; // 排除不可能的索引
}
}
}
测试用例：
@Test
public void isfindMedianSortedArrays() {
int[] nums1 = {1,2};
int[] nums2 = {1, 2, 3,4, 4, 5, 6, 7, 8, 9, 10}; //
double i = findMedianSortedArrays(nums1, nums2);
Assert.assertNotNull(i);
}
小結
这道题主要是考查了二分法的使用，做这道题需要注意各种情况以及边界的处理，这道题也可以通过递归的方式去实现，出口和本题一致。
热门推荐：
文末福利，最近整理一份面试资料《Java面试通关手册》，覆盖了Java核心技术、JVM、Java并发、SSM、微服务、数据库、数据结构等等。获取方式：GitHub github.com/Tingyu-Notes，更多内容关注我的简书，陆续奉上。
网友评论