Dorado's host
首页
日常
追番
随笔
工作
技术杂项
开源项目
学习
java基础
mit 6.S081
算法
写题目
学知识
友链
留言
关于我
登录
首页
日常
追番
随笔
工作
技术杂项
开源项目
学习
java基础
mit 6.S081
算法
写题目
学知识
首页
›
写题目
›
寻找两个正序数组的中位数
寻找两个正序数组的中位数
2022-01-24 01:22
1237
0
## 废话 上一次写blog是好久之前了....orz 刚搬到了新家,原先的室友兼同事兼高中同学拿到offer回学校玩耍去了QAQ,导致我不得不搬到了现在的合租4k房(魔都的房价真是够了) 最近在看《MySQL是怎样运行的》,很不错的一本书,目前的进度是看完第三章了,考虑如果看完很有帮助的话可以写一篇blog推推 言归正传,写道题 ## 题目描述 给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (m+n)) 。 > 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays ## 初看 乍一看,sb题鸭,可以这么写简单过 建个数组,排个序 ```java import java.util.Arrays; class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int n = nums1.length; int m = nums2.length; int[] nums = new int[n + m]; System.arraycopy(nums1, 0, nums, 0, n); System.arraycopy(nums2, 0, nums, n, m); Arrays.sort(nums); if ((m + n) % 2 == 1) { return nums[(n + m) / 2] * 1.0; } else { return (nums[(n + m) / 2] + nums[(n + m) / 2 - 1]) / 2.0; } } } ``` 时间复杂度:O((n+m) * log(n+m)) 空间复杂度: O(n+m) ![](https://dorado.host/usr/uploads/2022/01/3275001777.png) ## 乍一看 想一下,应该还有优化,两个有序数组没必要直接快排,直接排序阶段可以用O(m+n)的算法 和上面都不变,唯一的改变是换个排序方式 ```java import java.util.Arrays; class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int n = nums1.length; int m = nums2.length; int[] nums = new int[n + m]; int i1 = 0, i2 = 0; int cnt = 0; int key = 0; while (i1 < n && i2 < m) { if (nums1[i1] < nums2[i2]) { key = nums1[i1++]; } else { key = nums2[i2++]; } nums[cnt++] = key; } if (i1 == n) { for (int i = i2; i < m; i++) { nums[cnt++] = nums2[i]; } } if (i2 == m) { for (int i = i1; i < n; i++) { nums[cnt++] = nums1[i]; } } if ((m + n) % 2 == 1) { return nums[(n + m) / 2] * 1.0; } else { return (nums[(n + m) / 2] + nums[(n + m) / 2 - 1]) / 2.0; } } } ``` 时间复杂度:O(n+m) 空间复杂度: O(n+m) ![](https://dorado.host/usr/uploads/2022/01/1057985880.png) ## 发现真相 交完又看了眼题面,woc,题面上说要用log(n+m) QAQ,我O(n+m*log(n+m))的写法居然没给我t...... 思考一下,一般log的解法就是用二分,但是如何在两个有序数组里做二分查找呢? 首先明确想法,找中位数其实就是找第(m+n)/2小的数(奇数)或(m+n)/2和(m+n)/2+1小的数 那么问题转换为如何在两个有序数组里找到第k个小的数呢? 首先这样思考,我们可以先比较nums1[k/2 -1]和nums2[k/2-1],对比完之后,如果nums1[k/2-1] < nums2[k/2-1],则此时nums1[k/2-1]至多为第k-1个数(极端场景下nums1[k/2-1] > nums2[0:k/2-1]),此时可以将nums1[0:k/2-1]舍去 (仔细理解) ![](https://dorado.host/usr/uploads/2022/01/607301260.png) (上图来源leetcode:) 此后我们用二分不断逼近后面的第k大数 我们需要根据被减少掉的数字来减k,因为本质上我们就是在剩下来的数组里二分查找第k大的过程,当数据范围少了一部分,k理应减小 此时有三个临界点: 1. 如果数组越界,那么我们可以选取对应数组中的最后一个元素。在这种情况下,我们必须根据排除数的个数减少 k 的值,而不能直接将 k 减去 k/2。 2. 如果一个数组为空,说明该数组中的所有元素都被排除,我们可以直接返回另一个数组中第 k 小的元素。 3. 如果 k=1,我们只要返回两个数组首元素的最小值即可。 其中1,2很好理解,3的话此时我们已经排除调了前k-1个数了,此时两个数组头部最小的数就是第k小的数了 代码如下: ```java import java.util.Arrays; class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int len1 = nums1.length, len2 = nums2.length; int len = len1 + len2; if (len % 2 == 1) { return getKth(nums1, nums2, len / 2 + 1); } else { return (getKth(nums1, nums2, len / 2 ) + getKth(nums1, nums2, len / 2 + 1)) / 2.0; } } public double getKth(int[] nums1, int [] nums2, int k) { // 取nums1[k / 2 - 1] 和 nums2[k / 2 - 1] 的数对比,谁小则证明该数至少要比前 k - 2 个数要小(此时k为第k-1小),所以比该数小的序列都去掉 // 去掉之后,相当于找接下来的数里第(k - (删除的数量))小的数 // 特殊情况: // 1. 当 nums1[k/2-1]或nums2[k/2-1]越界,则取末尾 // 2. 当其中一个数组为空,则找另一个数组里第k小的数 // 3. 当k = 1,此时已经去掉了k-1个数了,此时两个数组的头部最小的数即为两个原数组内最小的第k个数 int len1 = nums1.length, len2 = nums2.length; int i1 = 0, i2 = 0; while (true) { if (i1 == len1) { return nums2[i2 + k - 1]; } if (i2 == len2) { return nums1[i1 + k - 1]; } if (k == 1) { return Math.min(nums1[i1], nums2[i2]); } int mid = k / 2; int new_i1 = Math.min(i1 + mid, len1) - 1; int new_i2 = Math.min(i2 + mid, len2) - 1; if (nums1[new_i1] <= nums2[new_i2]) { k -= (new_i1 - i1 + 1); i1 = new_i1 + 1; } else { k -= (new_i2 - i2 + 1); i2 = new_i2 + 1; } } } } ``` 时间复杂度:O(log(m+n)) 空间复杂度:O(1) ![](https://dorado.host/usr/uploads/2022/01/410356610.png) ## 结尾 本题主要想考察二分查找,区别于以往的单有序数组的二分查找,双有序数的查找其实可以转化为第k大的问题然后利用二分查找。 可以睡觉了,zzzzzz
相关文章
评论
(暂无评论)
取消回复
发表评论
dorado
一个平平无奇的打工人
17
文章
1
评论
12
栏目
热门文章
寻找两个正序数组的中位数
0 评论
ubutnu下的git常用命令
0 评论
IDEA快捷键一览(转)
0 评论
每日一报自动点击脚本
0 评论
端口查询
0 评论
更多