企业官网建设流程全解析

先说明：Hard不是另一个世界。

过去的绝大多数中等题和Hard的差别，往往只隔一层——多一个边界、多一个维度、多一份状态。

LC.41比LC.448多的只是“不能开额外空间”，LC.460比 LC.36多的只是“同频再比时间”。

LC.4把三层一次压满：你用的还是二分、单调性、循环不变量，只是被二分的那个东西，从“数组里的下标”变成了“两个数组里的分割点”。

今天三件事：把分割点二分（partition point search）讲透、把j = (m+n+1)//2 - i从公式变成推出来的结论、用实测看清 O(logn) 与O(n)的差距怎么随规模拉开。

📦 题目速览 Leetcode 4（30秒读懂）

给定两个非递减整数数组nums1、nums2，返回合并后的中位数。

要求O(log(m+n))时间，且不能真构造合并数组。

示例：

• [1,3],[2]→2.0
• [1,2],[3,4]→2.5
• [],[1]→1.0
• [-5,-3],[-2]→-3.0

⚠️最后一行是负数边界：合并后[-5,-3,-2]，中位数是−3不是−2。

正数跑通不代表负数跑通——我第一版就顺手写成了 −2，被断言脚本当场抓住。

🧠 核心思路

为什么不能真合并？

线性归并——双指针扫一遍拼成新数组再取中间——正确性无可挑剔，但有两个硬伤：时间不合规（O(m+n) 对 O(log(m+n))）、空间不合规。

更根本的是它回避了一个问题：求中位数到底需要多少信息？

答案是“很少”：中位数只涉及合并序列里的第⌊(m+n)/2⌋个和第⌊(m+n)/2⌋+1个，其余元素只需满足不比这两个位置更小——而这个约束，用两个数组各自的有序性就能直接读出来。

这就是二分的入口：把“答案的位置”当成待求量去二分，而不是把元素逐个取出来比较。

换个模型：虚拟合并

假设存在一个已排序数组M = merge(nums1, nums2)。

它是虚拟的，只存在于想象中，一个格子都不会被分配。

问题变成：在M里找一条分割线让左右两半平衡。

而M是两段拼的，切一刀等价于在两个数组里各切一刀：nums1切在i，nums2切在j。

nums1（下标 0..m-1） nums2（下标 0..n-1） ┌──────────┬──────────┐ ┌──────────┬──────────┐ │ L1 区域 │ R1 区域 │ │ L2 区域 │ R2 区域 │ │ [0, i-1] │ [i, m-1]│ │ [0, j-1] │ [j, n-1]│ └──────────┴──────────┘ └──────────┴──────────┘ ↑ ↑ 分割点 i 分割点 j

四个边界随之确定：L1 = nums1[i-1]、R1 = nums1[i]、L2 = nums2[j-1]、R2 = nums2[j]，越界的那一个不存在。

每个边界都读“隔壁那一侧”：L1是左边最后一个，R1是右边第一个。

核心推导：j为什么等于half - i

第一步：左半该放几个元素？

设s = m + n。奇数时答案是下标(s-1)/2的那一个元素；偶数时是下标s/2 - 1与s/2的平均——这两个候选必须跨越分割线，一个在左半末尾、一个在右半开头。于是“左半容量”是⌈s/2⌉：

half = (m + n + 1) // 2

s为奇数时它等于(s+1)/2，左半比右半多一个；s为偶数时它等于s/2，两半相等。

第二步：容量约束写成等式。左半总共half个，由L1与L2拼成，故i + j = half。

第三步：解出j——j = half - i = (m + n + 1) // 2 - i。

⚠️那个+1到底在干什么？奇数时它让左半多出来的那一个元素恰好就是中位数本身——左半最后一个正是max(L1, L2)，正坐在下标(s-1)/2上。

奇数时答案直接取max(L1, L2)；偶数时两半等大，max(L1, L2)与min(R1, R2)夹住中位数，取平均即可。

这个公式于是从“不知道该背还是该推”变成了“左半容量”的另一种写法，还顺手送出一件武器：i每加1，j就必须减1——j根本不是自由变量。这叫把二维约束压成一维，正是二分能启动的前提。

合法条件与收缩方向

设i增大（等价j减小）：L1与R2一大一小，L2与R1一小一大。

于是L1 <= R2只会越来越容易成立，L2 <= R1只会越来越容易不成立。

一个变好一个变坏不影响结论：同时满足两者的i构成一个连续区间，二分找它即可。

为什么“交叉处无逆序”就等价于“分割合法”？两个数组各自有序，M的有序性只可能坏在两处交界，而这两个条件合起来就是M左半 ≤M右半，再叠加“每半内部本来有序”便足以定位中位数。

⚠️ 易错点①：为什么必须在较短数组上二分

这是正确性前提，不是性能优化。

在较长数组上二分时i可取0..m（m= 较长长度），则j = half - i落在[half - m, half]，一旦i > half，j就是负数。

例如nums1 = [1,2,3,4,5]、nums2 = []，half = 3，在nums1上二分i=4时j = -1，直接越界。

开头那行交换是刚需：交换后m ≤ n，half ≥ m且half ≤ n（均因m ≤ n），故j ∈ [0, n]，越界不可能发生。

⚠️ 易错点②：边界上的 ±∞

i = 0时左半为空，L1不存在；i = m时右半为空，R1不存在，L2、R2同理。

要避开的两个坑：直接取nums1[i-1]（越界），或随手填0（会污染答案——0可能就是中位数本身）。

标准做法是补一个“永远不参与竞争”的哨兵：左侧补−∞，右侧补+∞。这样L1 <= R2在缺位时恒成立，判定里不需要任何if i == 0的特判。

哨兵的职责就是让边界融进主体逻辑——和lo/hi哨兵同理，只是那次在下标，这次在值域。

双语言差异：Python 有内置float('-inf')/float('inf')，直接用。

Java的float虽有Float.NEGATIVE_INFINITY，但数组是int[]，与float比较会隐式提升，取最大值时int会被提升成float再转回来，坑一层套一层，干净做法是用Integer.MIN_VALUE/Integer.MAX_VALUE。

int极值代替±∞在这题可接受（值域距±2^31差五个数量级），前提是哨兵一定落在有效值域之外。

🖼️ 图解算法（手把手走一遍）

主线用官方例2：nums1 = [1,2]，nums2 = [3,4]，m=2, n=4，half = 3，左半3个、右半3个（偶数，等分）。

第1轮i = 1，j = 2：

nums1 = [ 1 | 2 ] L1=1 R1=2 nums2 = [ 3 | 4 ] L2=4 R2=+∞

L1(1) <= R2(+∞)✅，但L2(4) <= R1(2)❌ ⇒ 左边切少了 ⇒lo = 2。

第2轮i = 2，j = 1：

nums1 = [ 1 2 | ] L1=2 R1=+∞ （i = m，右侧为空） nums2 = [ 3 | 4 ] L2=3 R2=4

两条件都 ✅ ⇒命中。m+n = 6偶数，取(max(2,3) + min(+∞,4)) / 2 = 3.5。

max(L1,L2) = 3是M = [1,2,3,4]的下标2元素，min(R1,R2) = 4是下标3元素——正好就是中位数要平均的那两个数。

L1明明是2，为什么左半最后一个不是2？

因为左半由nums1[0:2]=[1,2]与nums2[0:1]=[3]拼起来，最后一个是max(2,3)——max(L1, L2)就是“两条边里的较高者”。

💻 代码实现（Python + Java）

Python版

classSolution:deffindMedianSortedArrays(self,nums1:List[int],nums2:List[int])->float:INF=float("inf")# ① 必须在较短数组上二分，否则j会越界iflen(nums1)>len(nums2):nums1,nums2=nums2,nums1 m,n=len(nums1),len(nums2)# ② 左半容量：奇数时比右半多一个，偶数时两半相等half=(m+n+1)//2lo,hi=0,mwhilelo<=hi:i=(lo+hi)//2# ③ i加1则j减1；j不是自由变量j=half-i# ④ L取分割线左侧最后一个，R取右侧第一个l1=nums1[i-1]ifi>0else-INF r1=nums1[i]ifi<melseINF l2=nums2[j-1]ifj>0else-INF r2=nums2[j]ifj<nelseINF# ⑤ 两处跨界都无逆序 ⇒ 找到合法分割点ifl1<=r2andl2<=r1:if(m+n)%2==1:returnfloat(max(l1,l2))return(max(l1,l2)+min(r1,r2))/2.0ifl1>r2:# i偏大hi=i-1else:# i偏小lo=i+1raiseValueError("bad input")

Java版

classSolution{publicstaticdoublefindMedianSortedArrays(int[]nums1,int[]nums2){if(nums1.length>nums2.length){int[]t=nums1;nums1=nums2;nums2=t;}intm=nums1.length,n=nums2.length;inthalf=(m+n+1)/2;intlo=0,hi=m;while(lo<=hi){inti=(lo+hi)/2,j=half-i;intl1=(i>0)?nums1[i-1]:Integer.MIN_VALUE;intr1=(i<m)?nums1[i]:Integer.MAX_VALUE;intl2=(j>0)?nums2[j-1]:Integer.MIN_VALUE;intr2=(j<n)?nums2[j]:Integer.MAX_VALUE;if(l1<=r2&&l2<=r1){if(((m+n)&1)==1)return(double)Math.max(l1,l2);return(Math.max(l1,l2)+(double)Math.min(r1,r2))/2.0;}if(l1>r2)hi=i-1;elselo=i+1;}thrownewIllegalArgumentException("bad input");}}

⚠️防坑提醒（必看）：

• 别忘开头交换——在长数组上二分会推出负数的j。
• half的+1不能省——写成(m+n)//2时奇数情形中位数会掉进右半。
• 哨兵不能填0——0可能就是中位数本身。
• Java求平均要先提升再相加——Math.max + Math.min在int下可能溢出。

⏱️ 复杂度分析（面试必问）

• 时间：二分区间[0, m]，m = min(原两数组长度)，每轮折半 ⇒O(log(min(m,n) + 1))，比题目要求还紧。
• 空间：只有四个边界值和两个指针，O(1)——虚拟合并数组从头到尾没被构造。

🚀 举一反三：3道高频变体题

追问1：改成“求第k小”怎么做？

把“左半容量固定为⌈(m+n)/2⌉”换成“固定为k”：左半放k个 ⇒i + j = k⇒j = k - i；判定条件一字不改；返回值不看奇偶，统一返回max(l1, l2)。整段只动了两个字符（half→k）。

这顺带把“对第 k 小做分割点二分”解释清楚了：中位数只是第k小在k = ⌈(m+n)/2⌉时的特例。

追问2：数组无序怎么办？

必须说清楚：二分这套整体失效。

地基是“两数组各自有序 ⇒M的有序性只在两处交界被破坏”；地基没了，L1、R1不再分别代表“左半最大”和“右半最小”，L1 <= R2也失去判别能力。

三条退路：

① 先排序再套本解法（能过但考点全废）；
②改成堆——两堆分装大小两半、规模差不超过1，插入O(logn)、取中位数O(1)，这是对顶堆（LC.295）；
③ BFPRT 随机选择，期望 O(n)。

追问3：O(log min(m,n)) 怎么来的？为什么是min不是m+n？

因为二分的对象是i，而i是较短数组里的分割点，范围[0, m]（m = min），二分长度m的区间就是log(m)。

更值得炫的是：j不是二分变量，它是被i决定的函数——若同时在两个数组上二分，状态是(i, j)的二维平面，你根本没有“每轮折半”这回事。

这个“二维化一维”的手法比今天这道题更值得记住，它会在 LC.719、LC.410 原样回来。

对照

一句话读法：经典二分的判据是“这个位置的值和我要的比什么”，今天换成“这个切法让左右两半的关系成立吗”。骨架一模一样，判据换了，维度升了一级。

🎁 今日总结

二分的骨架从没变过——在单调结构上找分界点；变的是被二分的结构。

今天我们把它从“数组里的下标”换成“虚拟合并序列上的分割点”，三个具体结论：

1. j = (m+n+1)//2 - i是推出来的，不是背出来的。half就是“左半容量⌈(m+n)/2⌉”，那个+1的作用是让总数为奇数时左半多出的那个恰好是中位数。
2. 在较短数组上二分是正确性前提，不是性能优化。长数组上二分会推出负数的j。
3. ±∞ 哨兵把边界融进主体逻辑。Python用float('inf')，Java用int极值，后者要求值域离±2^31足够远。

再上一层是那个更普适的：把二维约束化成一维。今天它是j = half - i，下周它会以别的形式回来。