叭叭一下如果某个cs门人焦虑了那那些学成男娘或秃头的人一定会说“什么你有时间焦虑”题目描述给定两个大小分别为m和n的正序从小到大数组nums1和nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为O(log (mn))。示例 1输入nums1 [1,3], nums2 [2] 输出2.00000 解释合并数组 [1,2,3] 中位数 2示例 2输入nums1 [1,2], nums2 [3,4] 输出2.50000 解释合并数组 [1,2,3,4] 中位数 (2 3) / 2 2.5提示nums1.length mnums2.length n0 m 10000 n 10001 m n 2000-106 nums1[i], nums2[i] 106分析要求求合并后的数组的中位数即使归并也需要mn复杂度复杂度要求log(mn)需要结合折半的思想才行最小k值法:转化为取第k小元素k为组合后长度一半 每次递归淘汰一半元素 最后得到第k小元素思路1最小k值法OK两数组长度m n那么中位数在(m n 1) / 2 和(m n 2) / 2位置奇数个两值相等偶数个为平均值那么怎么找到两个值首先取k分别为这两个值在两个数组中分别取k/2位置比较两个值对小的一个第k小元素肯定不在这个数组前k/2位置因为如果在这里的话假设为x这一半最多k/2个小于等于x另一个数组最多k/2-1个小于等于x这样最多k-1个小于等于x那x最多就是第k-1小的元素所以第k小元素不可能在这里。所以可以删去这k/2个元素既然已经删去了比第k小元素小的k/2个元素那问题转化为求剩下元素的第k-k/2小元素这样递归下去每次砍k/2的l次方元素直到k砍到为1直接取最小的那个就行了--这是一个递归退出条件。另一个递归退出条件是某个数组用尽直接在另一个数组取需要的值就行了。另外在比较的时候假如某个数组剩余长度小于当前k/2那就直接在另一个数组取要舍去的一半因为这一半已经不够舍去了(元素数小于k/2)所以另一个数组小于第k的元素一定多于k/2(否则总数不够k-1)。操作如下将问题转换为求两个有序数组合并后的第k小元素其中k (mn1)/2和k (mn2)/2处理奇偶。定义函数getKth(nums1, start1, nums2, start2, k)若其中一个数组已经用完直接返回另一个数组的当前第 k 个元素。若 k 1返回两个数组当前起始位置的最小值。否则比较两个数组的第k/2个元素若不够则取最后一个剔除较小元素所在数组的前 k/2 个元素递归查找剩余部分。最终中位数为两个k位置的平均值奇数时两次相同。时间复杂度每次递归减少 k/2递归深度 log(mn)满足要求。代码如下class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m nums1.length; int n nums2.length; int left (m n 1) / 2; int right (m n 2) / 2; return (getKth(nums1, 0, nums2, 0, left) getKth(nums1, 0, nums2, 0, right)) / 2.0; } public double getKth(int[] nums1, int start1, int[] nums2, int start2, int k) { if(start1 nums1.length) return nums2[start2 k - 1]; if(start2 nums2.length) return nums1[start1 k - 1]; if(k 1) return Math.min(nums1[start1], nums2[start2]); int mid1 (start1 k / 2 - 1 nums1.length) ? nums1[start1 k / 2 - 1] : Integer.MAX_VALUE; int mid2 (start2 k / 2 - 1 nums2.length) ? nums2[start2 k / 2 - 1] : Integer.MAX_VALUE; if(mid1 mid2) { return getKth(nums1, start1 k / 2, nums2, start2, k - k / 2); } else { return getKth(nums1, start1, nums2, start2 k / 2, k - k / 2); } } }另外附上我的个人网站作分享交流大圣的技术空间 - 沉心砺骨 向阳而生