LeetCode 4 寻找两个有序数组的中位数

背景

我会的语法程度就是会几个if else for 的程度。
算法确实大学里面是有课程，但是我大学都逃课来着。所以顶天就是知道快速排序这几个字怎么写。
目标就是通过此次学习提高一下自己的能力。

源码仓库

题目

英文版本

中文版本

本文具有强烈的个人感情色彩,如有观看不适,请尽快关闭. 本文仅作为个人学习记录使用,也欢迎在许可协议范围内转载或使用,请尊重版权并且保留原文链接,谢谢您的理解合作. 如果您觉得本站对您能有帮助,您可以使用RSS方式订阅本站,这样您将能在第一时间获取本站信息.

解题思路

第一次审题

两个有序数组，找中位数。算法时间复杂度要求 O(log(m + n))。
第一个反应是如何把两个有序数组合并成一个有序数组。 然后我根本不记得各种排序算法的时间复杂度。所以 Google 出来

[时间复杂度] (https://zh.wikipedia.org/wiki/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6)

貌似没有一个排序的时间复杂度是 O(log(n)) 级别的。 快排的是 O(nlog(n)). 唯一一个表里的 O(log(n)) 级别的是二分搜索。

点过去看 二分搜索算法 的详细解释。有序数组和O(log(n))的关键字出现使得感觉就是本题所需要的算法。

然后，就陷入了一个自我的错误逻辑里面，如何把两个数组合并为一个数组并且使用二分搜索。结果苦思冥想了一天，毫无结论。卡住了。

看了别人的分析以后的第N次审题

我先跟JJS讨论了下，恰好他几个月前也做了。他说了他的思路给我。一种Cut法，然后一顿给我操作。在他哪里可以各种解决的情况，在我这里就没法想明白。没办法本来是觉得这次做题就不看别人自己解答的，但是还是忍不住找了解题来看。
就看了 扁扁熊题解

然后就高山仰止了。先把问题抽象成了数学问题解了。然后才是代码的完成。羡慕这样的能力。接下来我看了至少3遍以上的分析，确保自己明白了。然后记录下解题自己需要注意的地方。

解题要点

中位数的定义
将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。此时元素较小的子集的最大值和元素较大的子集的最小值的平均值就是中位数

由于集合个数并没有特别的规定。为了使得定义中一个子集和另外一个子集的长度相等。所以存在偶数组和奇数组的不同划分方式。

1. 奇数组因为除2没法刚刚好的划分为两个长度相等的子集，就把最中间的那个数看作都在两个集合里面，。例如 [1, 3, 100] 划为 [1,3] [3, 100]. (3 + 3) / 2 = 3, 3就是中位数;
2. 偶数组因为除2刚刚好的划分为两个长度相等的子集。例如[1, 5, 50, 100] 划为 [1,5] [50, 100]. (5 + 50) / 2 = 27.5 就是中位数

从上面的到的结论就是：

情况1: 子集的个数 = (原集合奇数个 + 1) / 2
情况2：子集的个数 = 原集合偶数个 / 2

然后继续解题，如果我们想要求出中位数就是需要把两个有序数组，合并起来以后划分为两组，两组元素相等，另一组的最大值小于等于另一组的最小值。

使用题目给出的参数进行数学化：
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

m + n 为偶数情况
l = (m + n) / 2
使用nums1其中的前i个元素和nums2前j个元素组成新的数组smaller_nums, 其他元素组成新的数组larger_nums
因为i + j = l 是必须要满足的情况，l为已经已知, 所以我们遍历i的时候可以的到j。
只要max(smaller_nums) < min(larger_nums) 的时候，我们就得到了满足中位数的两个集合。 此时 (max(smaller_nums) + min(larger_nums))/ 2 中位数

m + n 为奇数情况
l = (m + n + 1) / 2
使用nums1其中的前i个元素和nums2前j个元素组成新的数组smaller_nums, 其他元素组成新的数组larger_nums
因为i + j = l 是必须要满足的情况，l为已经已知, 所以我们遍历i的时候可以的到j。
只要max(smaller_nums) < min(larger_nums) 的时候，我们就得到了满足中位数的两个集合。此时max(smaller_nums) 就是中位数

最后 如果i真的是从0开始遍历， 那么时间复杂度应该是O(n)
所以，我们使用二分法来进行 i 的遍历。

扣题完美。

我根据上面的分析并没有写出合适的程序来，边界条件一直模糊。
最后又看了一遍官方的数学推导过程。

官方解题

才勉勉强强写出程序来。

后记

AWS 学的断断续续，感觉没激情。总感觉，如果工作中需要AWS，到时候怼着文档和 Google 应该是能解决问题怼。就不想看了。但是还是要提升自己。所以想了想找 LeetCode 来学习一下算法好了。 还是写代码来的踏实。

硬广时间

我目前现生活在新西兰。

如果是新晋奶爸可以看看婴儿奶粉

如果逢年过节孝敬父母可以逛逛澳新保健品

如果经常熬夜或喝酒，你需要程序员神器-护肝片

大量澳新产品均可通过么么爪海购精选购买。

么么爪海购精选上的价格在海外直邮模式上有一定优势，但是跟国内电商上大量低价商品没法比。优势上只能用我自己那可能并不存在的人品担保都是正品。