困难的二分算法｜周末学习

这是我参与更文挑战的第6天，活动详情查看：更文挑战

本文已参与 周末学习计划，点击查看详情

寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

思路分析

最简单的方法自然是先merge再根据数组长度总和决定是使用索引n/2还是索引n/2和n/2 + 1相加除以2.

这个方法的时间复杂度是是O（n）

空间上也需要开辟一个大数组。

那么有没有更好的办法呢？

其实在已知二分的方式解题后，我们就可以照着箭头画靶子了，首先分析题干本身：

• 两个有序数组，中位数是一个数字，如果数组长度总和是奇数，那就是数组整合后排在中间的数，如果数组长度总和是偶数，那就是数组整合后排在中间左右两边的和。

• 对于一个长度为8的数组，size=7，那么中位数为索引7/2 和 7/2 + 1的数字，

• 对于一个长度为7的数组，size=6，那么中位数索引为6/2 =3的数字

• 我们发现可以找size/2的一条线，线的左边数量一定是size/2 – 1个（因为线本身是一个）

• 由于两个数组，所以很可能数组不具备中位数，所以将线的定义改为左边的数量size/2-1个（相当于线只是线，不再是一个元素，线的右边第一个元素或者第一个第二个元素取平均即中位数）。（这里有种sql自连接排序的感觉）

• 所以如果第一个数组A的线左边数量有x个，第二个数组B的线左边数量就有y=size/2-1-x个。

• 即有[0,size/2-1],[1,size/2-2],[2,size/2-3],…,[m – 1,size/2 – m]

• 那么时间复杂度就被降低成为两个数组较小的一个m了。

那么如何分析这条线是否合理呢

其实很简单只要线左边的最大值，小于线右边的最小值即可
即

max(arr[i],arr1[j]) < min(arr[i + 1] , arr1[j + 1])
复制代码

写到这里这道题就没啥分析的价值了，剩下的就是看看边界条件的分析了，多写几个if的事