Loading... # [寻找两个正序数组的中位数](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/description/) | Category | Difficulty | Likes | Dislikes | | :-: | :-: | :-: | :-: | | algorithms | Hard (38.31%) | 2827 | - | 给定两个大小为 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 ``` --- [Discussion](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/comments/) | [Solution](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/) ## 读题 这题其实难度不在于寻找中位数,而在于题目要求 **复杂度log(m+n)** 由于LeetCode的答案检查并没有评估复杂度,所以很多非**复杂度log(m+n)** 的算法也能过, **但是作为一个程序员,甲方提出的要求能满足还是满足吧(只需要默默地骂他一句 SB 就行了)** 熟悉复杂度和基本算法的同学看到log,可能就知道八九不离十要用二分查找了。 m+n 简单得理解为数组合并,而且还要按照大小排序的话,复杂度可能就不止 **log(m+n)** 了。 所以问题的核心在于,不用合并,对于两个已经排序好的数组,如何使用二分法查找。 ### 二分法 二分法说的形象一点,就是玩猜数字游戏。 0-100,猜中的有奖。 如果不考虑运气,最快的猜中方法是什么? **猜中间那个数!** 她可以快速缩小范围,排除最多的无效数,这就叫,二分法。 法如其名:二分法的精髓在于,一分为二!一般还是对半分! ## 解题 那么 <img src="https://traceless.tech/usr/themes/handsome/assets/img/emotion/aru/meditation.png" class="emotion-aru"> 问题来了,如何二分! <img src="https://traceless.tech/usr/themes/handsome/assets/img/emotion/aru/speechless.png" class="emotion-aru"> oh my god 没有思路! 别急,俗话说得好 **“努力的人一定能被看见”** 凡事都是化繁为简的一个过程,我们按照普通思路,抛开复杂度的解法 比较容易想到,可以使用是遍历两个数组合并成一个新数组,最后寻找中位数的方式完成本题 代码如下: ```C# // @lc code=start public class Solution { //不看题目的复杂度要求,很容易想到排序算法,刚好题目中的两个数组本身就是排好序的,其实问题的关键是:两个已经排好序的数组如何合并为一个排好序的数组,最后根据数组长度的奇偶就很容易得到中位数了 public double FindMedianSortedArrays(int[] nums1, int[] nums2) { int length1 = nums1.Length; int length2 = nums2.Length; int[] finalArr = new int[length1 + length2]; int left = 0; int right = 0; for (int i = 0; i < length1 + length2; i++) { if (left > nums1.Length - 1) { //到头了 finalArr[i] = nums2[right]; right++; continue; } if (right > nums2.Length - 1) { finalArr[i] = nums1[left]; left++; continue; } if (nums1[left] <= nums2[right]) { finalArr[i] = nums1[left]; left++; } else { finalArr[i] = nums2[right]; right++; } } if (finalArr.Length % 2 == 0) { return (finalArr[finalArr.Length / 2] + finalArr[finalArr.Length / 2 - 1]) / 2.000; } else { return finalArr[finalArr.Length / 2]; } } } // @lc code=end ``` 这种解法的思路很简单,代码里就不详细讲解了,相信你这个小机灵鬼看代码就懂了 <div class="tip inlineBlock info"> ```C# if (finalArr.Length % 2 == 0) { return (finalArr[finalArr.Length / 2] + finalArr[finalArr.Length / 2 - 1]) / 2.000; } else { return finalArr[finalArr.Length / 2]; } ``` </div> 注意到上面这段代码,利用了中位数的性质 从根本上是:取有序数组中,第k小的数【k=(m+n)/2】, 偶数情况下是 **第k小**与 **第k+1** 小数的平均值。 <img src="https://traceless.tech/usr/themes/handsome/assets/img/emotion/aru/discovertruth.png" class="emotion-aru"> 二分法,第k小,oh my god! 利用中位数是k=(m+n)/2和本身排好序的特点,取k=(m+n)/4位置【保证m+n的中位数不会被切掉】,逐个二分逼近中位数! <img src="https://traceless.tech/usr/themes/handsome/assets/img/emotion/aru/clap.png" class="emotion-aru"> 真是个小机灵鬼 具体图解就不上了【画图好麻烦!】 [可以参考本链接 解法三][2] 其实理解起来没有那么简单,但是也不算复杂。 实际在实现中,需要考虑几个问题 1.数组边界 2.索引转化 3.变值k的变化及其边界 4.其它我忘记说的东西 <img src="https://traceless.tech/usr/themes/handsome/assets/img/emotion/aru/proud.png" class="emotion-aru"> ```C# // @lc code=start public class Solution { //题目的关键是复杂度为log(m+n) ,log(m+n)一般就要想到“二分法”,中位数的性质决定,左边一半的数组小于等于中位数,右边一般的数组大于等于中位数,本身又是排好序的,问题转化为,从两个有序数组中寻找第K小的数[k=(m+n)/2] public double FindMedianSortedArrays(int[] nums1, int[] nums2) { int n = nums1.Length; int m = nums2.Length; int len = n + m; int pre = (len + 1) / 2; int k = (len + 2) / 2; if (len % 2 == 0) return (findKTh(nums1, 0, n - 1, nums2, 0, m - 1, pre) + findKTh(nums1, 0, n - 1, nums2, 0, m - 1, k))/2; else return findKTh(nums1, 0, n - 1, nums2, 0, m - 1, k); } public double findKTh(int[] nums1, int s1, int e1, int[] nums2, int s2, int e2, int k) { //计算长度 int len1 = e1 - s1 + 1; int len2 = e2 - s2 + 1; if (len1 > len2) { //比较大小,保证1<2,防止溢出 return findKTh(nums2, s2, e2, nums1, s1, e1, k); } if (len1 == 0) { //短数组没了,直接取长数组中的值 return nums2[s2 + k - 1]; } if (k == 1) { //取第1小的数,表示取最小,两个数组的起始中最小的取出来就行了 return nums1[s1] > nums2[s2] ? nums2[s2] : nums1[s1]; } //取索引,防止数组越界,超过长度取最后一个 int i = s1 + Math.Min(len1, k / 2) - 1; int j = s2 + Math.Min(len2, k / 2) - 1; if (nums1[i] > nums2[j]) { //短数组值大于长数组,淘汰长数组前面j个数,相当于找第k + s2 - 1 - j小 //k + s2 - 1 - j的解释,k表示当前s2开头的数组为0,的第k小,所以在总数组中是第k+s2-1小,j:本次淘汰的个数 return findKTh(nums1, s1, e1, nums2, j + 1, e2, k + s2 - 1 - j); } else { return findKTh(nums1, i + 1, e1, nums2, s2, e2, k + s1 - 1 - i); } } } // @lc code=end ``` ### 思考 - 数理系大佬可能经过一波操作推导出中位数的什么不等式组,利用 **神奇的数字游戏** <img src="https://traceless.tech/usr/themes/handsome/assets/img/emotion/aru/surprised.png" class="emotion-aru"> 实现更快速复杂度更低的解法 - 为啥时间和占用空间和第一个理论上更差的算法差的不多甚至更大呢?【大概是leetcode代码运行有波动,测试用例不够全面反映算法问题?亦或,新算法的某些实现其实不符合理论上的推导,存在某些没注意到的高复杂度的部分没有发现?】 ### 膜拜大佬 如果大佬们有更好的解法,不如评论分享赐教~ [我的Leetcode解题代码库][1] [1]: https://github.com/traceless0929/.leetcode [2]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/ Last modification:October © Allow specification reprint Support Appreciate the author AliPayWeChat Like 0 如果觉得我的文章对你有用,请随意赞赏
One comment
滴!学生卡!打卡时间:上午9:41:51,请上车的乘客系好安全带~