LeetCode 4 寻找两个正序数组的中位数hard 题但思路不复杂——转化为找第 k 小的数每次二分砍掉一半。 寻找两个正序数组的中位数两个正序数组找它们合并后的中位数。要求 O(log(mn))。[1,3], [2] → 2.0推导链两个有序数组找中位数 → 合并再取中间是 O(mn)不符合。中位数本质是第 k 小的数。每次从两数组各取 k/2 个比较末尾小的那一半不可能包含第 k 小的数它们加起来都不够 k 个可整段丢弃。每次砍一半。别想着真把两个数组合并——那是 O(mn)不符合要求。中位数 第 k 小的数k 总长度一半。每次从两个数组各取 k/2 个元素比较末尾小的那一半整体丢掉。每次砍一半log 级别。publicdoublefindMedianSortedArrays(int[]nums1,int[]nums2){inttotalnums1.lengthnums2.length;if(total%21){returnfindKth(nums1,0,nums2,0,total/21);}else{intleftfindKth(nums1,0,nums2,0,total/2);intrightfindKth(nums1,0,nums2,0,total/21);return(leftright)/2.0;}}privateintfindKth(int[]a,inti,int[]b,intj,intk){if(ia.length)returnb[jk-1];// a 用完了if(jb.length)returna[ik-1];// b 用完了if(k1)returnMath.min(a[i],b[j]);// 只剩一个了inthalfKk/2;intaValihalfK-1a.length?a[ihalfK-1]:Integer.MAX_VALUE;intbValjhalfK-1b.length?b[jhalfK-1]:Integer.MAX_VALUE;if(aValbVal)returnfindKth(a,ihalfK,b,j,k-halfK);// 丢掉 a 的前 halfK 个elsereturnfindKth(a,i,b,jhalfK,k-halfK);// 丢掉 b 的前 halfK 个}时间 O(log(mn))。数组越界处理取 a[i k/2 -1] 之前必须判断是否越界越界说明这个数组不够长给它塞一个 MAX_VALUE 让它永远比输自然砍另一个数组。k1 的边界剩最后一个要选的时候直接 min(a[i], b[j])不需要再比 k/2。取 a[ik/2-1] 前必须判越界——不够长时用 MAX_VALUE 占位在比较中自动输掉。k1 时直接 min(a[i], b[j])。这道题你踩过什么坑或者你用别的语言实现过吗评论区聊聊回头复习也方便翻。