LeetCode 4寻找两个正序数组的中位数 —— 二分查找法 题解 题目链接 https://leetcode.cn/problems/median-of-two-sorted-arrays/ 题目概要给定两个大小分别为m和n的正序从小到大数组nums1和nums2。请你找出并返回这两个正序数组的中位数。要求算法的时间复杂度应该为O(log(m n))。示例 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✅ 本题解法二分切割法最优解AC代码核心思想不合并数组直接在两个数组上做二分查找将两个数组左右切割让左半部分整体 ≤ 右半部分通过切割位置直接算出中位数始终把短数组作为 nums1减少二分次数 详细解题思路1. 核心原理数组切割把两个数组各分成左右两部分nums1左[0, i-1]右[i, m-1]nums2左[0, j-1]右[j, n-1]满足两个条件左半总长度 右半总长度或多1i j m - i n - j 1→ 推导得j (m n 1) / 2 - i左边所有数 ≤ 右边所有数nums1[i-1] ≤ nums2[j]且nums2[j-1] ≤ nums1[i]2. 边界处理左边没数用Integer.MIN_VALUE右边没数用Integer.MAX_VALUE3. 中位数计算总长度奇数左边最大值就是中位数总长度偶数(左边最大值 右边最小值) / 2.04. 二分调整切割点nums1[i-1] nums2[j]i太大 → 左移r i - 1nums2[j-1] nums1[i]i太小 → 右移l i 1✅ AC 代码classSolution{publicdoublefindMedianSortedArrays(int[]nums1,int[]nums2){if(nums1.lengthnums2.length){int[]tmpnums1;nums1nums2;nums2tmp;}intmnums1.length;//元素少的数组intnnums2.length;intl0,rm;while(lr){inti(lr)/2;intj(mn1)/2-i;//绳子总长减去i的长度intl1(i0)?Integer.MIN_VALUE:nums1[i-1];intr1(im)?Integer.MAX_VALUE:nums1[i];intl2(j0)?Integer.MIN_VALUE:nums2[j-1];intr2(jn)?Integer.MAX_VALUE:nums2[j];// 满足条件if(l1r2l2r1){if((mn)%21){returnMath.max(l1,l2);}else{return(Math.max(l1,l2)Math.min(r1,r2))/2.0;}}elseif(l1r2){ri-1;}else{li1;}}return0;}}⏱️ 复杂度分析指标复杂度说明时间复杂度O(log(min(m,n)))只对短数组二分空间复杂度O(1)只用常数变量 核心一句话总结在两个有序数组上做二分切割让左边整体 ≤ 右边满足长度平衡后直接从边界值计算中位数。 高频面试问答1. 为什么要把短数组放前面让二分次数变少保证时间复杂度O(log(min(m,n)))。2. 为什么 j 这么算j (m n 1) / 2 - i保证左右两边长度相等或左边多1方便取中位数。3. 为什么要用 MIN/MAX 处理边界防止数组越界同时不影响大小比较。最后记录一下第一遍刷完Leetcode的Hot100题。虽然有一些题是抄题解的。