Leetcode4号题

Question

波波老师可以更新一下leetcode4号题的java代码吗:)
如果能稍作解释就更好了,看了官方的解答 一脸懵

Answer 1

liuyubobobo 2019-06-13 17:17:30

我的参考代码（C++）：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0004-Median-of-Two-Sorted-Arrays/cpp-0004/main.cpp

==========

这个问题细节还挺多。我大概解释一下整体思路，很多细节需要你在一点一点思考调试：）

两个数组，比如一个是：a1 a2 a3 a4， 一个是 b1 b2 b3 b4 b5 b6

a和b都是有序的。

如果，我们这样切分a：a1 a2 | a3 a4

由于两个数组一共有10个元素，我们就知道，切分b的方法一定是：b1 b2 b3 | b4 b5 b6

这样才把整个数组切成了5, 5两部分。

怎么验证这个切分对不对呢？我们只需要看max(a2, b3)是不是小于等于min(a3, b4)就好了。也就是看左边的最大值是不是小于右边的最小值？

如果满足，我们的切分一定是对的。剩下的问题就是根据这个切分求median了。

这里有很多边界，需要处理整个数组是奇数还是偶数，包括切点左右是否有元素等问题

因为（a1 a2 a3 a4 | 空） 或者 （空 | a1 a2 a3 a4）也是合法的切分。

这部分比较繁琐，但整体很简单，随便举几个数组写写画画应该就能想明白。

对应我的代码：37-48行

如果这个切分不对呢？我们就需要改变这个切分。

所以，整体上，我们可以使用二分搜索的策略，只对a做切分。如果切分正确，求median；

否则，说明右边的最小值更小。如果右边的最小值就是a的右侧第一个值，我们对a的切分就可以往右移，否则就可以往左移。

对应我的代码51-54行。

最后，一个小优化，我们可以让nums1的大小永远小于等于nums2，这样，我们二分搜索一个更短的数组。

对应我的代码19行；

另外，如果nums1为空，此时就是求一个数组的median，特殊处理一下，对应我的代码22行。

加油！：）