Skip to content

Sixian Li

两个有序数组的中位数

LeetCode

暴力解:merge两个array,取中位数,复杂度O(N)O(N).

但这样的解法完全没有利用到这两个数组都是「有序」的这个信息。所以我们思考的时候,要考虑「有序」会给我们什么额外信息呢?

有序

这个中位数的特性就是,它一定能把array分成两部分,左边的都比它小,右边的都比它大。

A,B merge后的array, C, 的中位数,也能把这个array分成两部分。以下均假设C的长度是偶数(如果是奇数,一半的元素数量是floor(n/2) + 1,这一点在代码中有处理到)。如[1 2 3 4 5 6],那么它的一半的长度为3。由于这个数组里的全部元素都来自A和B,前半段里肯定有n1来自A,n2来自B。

如果我们知道n1,n2,能不能找到C的中位数呢?

设一半的长度为k,我们需要找到(C[k-1] + C[k])/2

因为A和B有序,第k个数是前半段最大的。An1-1Bn2-1分别是A和B里这部分最大的一个,那么只要找出他俩的max,这个数一定是前半段最大。同理,第k+1个数肯定来自于An1Bn2,他们要争夺「后半段最小」这个位置。

所以,如果知道n1n2,我们就能求到C的中位数。

怎么求n1和n2

首先,k是已知的,k=(len(A)+len(B))//2。如果知道了n1,可以通过n2 = k - n1求到n2。所以最终的问题是:如何找到n1?

我们可以理解为,我们把A切了一刀,分成两部分。由于k是固定的,我们也能知道B在哪里被切了一刀

这一刀左边属于C的前半部分,所以必然有L1R2,L2R1L_1\leq R_2, L_2 \leq R1。所以,如果这一刀切的位置是正确的,这两个条件一定成立。如果不成立,我们便可以排除掉一些元素。

如何排除元素

  • L1>R2L_1 > R_2

这种情况下,我们需要更小的L1,才有可能让它比R2小,那么这一刀得往左移,因为右边的都比L1大,绝对不可能小于R2。

  • L2>R1L_2 > R_1

我们需要更大的R1,所以这一刀得往右移。

移动多少呢?

我们自然是可以一个一个地移,但要知道,我们的目的是「尽快」找到一个L1L_1 ,从而使L1>R2L_1> R_2成立。这里要再次利用「有序」这个特点,引入binary search。

就好像猜数字那个例子,每一次我会告诉你,你的猜测是比我想的数大还是小,你自然可以一个一个地逼近我的答案。假设这个数在0到100之间,如果我想的是78,你猜的1,如果你按照1, 2, 3, …这个顺序来猜,再猜77次,可以猜对。但如果你用二分法,下一个你猜50,直接就排除掉了一半的元素。

这里也是一样,

我们可以确认新的L1来自区间[0, L1-1],那么我们先猜这个区间的中位数,如果还是太大,那整个[mid, L1-1]区间都可以被排除掉。这样肯定比一次挪一个有效率。

边界情况

实现中,我们的cut为R,L为R-1。当cut为0时,cut-1是不存在的。

先思考,如果正确的cut在a0,那么C的前k个元素里,没有任何来自a。那意思就是,a0大于等于b0, b1 ... bk-1。由于bk1b_{k-1}是最大的一个,只需要确定a0bk1a_0 \geq b_{k-1}是否成立,即L2R1L2\leq R1。在这个比较中,我们并不需要L1R2L_1 \leq R_2。为了让边界一般化,不比较,等同于这个条件always true,这样对后来的比较不会造成任何影响。那么,L1=MIN_INTEGERL_1 = \text{MIN\_INTEGER}就能保证它小于等于任何R2。同理,当我们想无视L2R1L_2 \leq R1时,只需要R1=MAX_INTEGERR_1 = \text{MAX\_INTEGER}

代码和几个细节

  1. 为什么一定要在短的那个里搜索?

    我们需要保证k-cut1是一个非负数,因为最少也就是有零个元素来自某个数组。

    k=(n1+n2)/2k = (n_1 + n_2) / 2。但如果我们不选择短的那个,cut1就有可能大于k。那为什么短的那个不可能出现cut1 > k?

    我们限制了cut1n1n2cut_1 \leq n_1 \leq n_2, 如果cut1>kcut_1 > k,那么n1+n2>2kn_1 + n_2 \gt 2k。如果C的长度是偶数,k正好是一半的元素,这个自相矛盾;如果是奇数,k为一半的元素加一,比一半的元素还多,2k更是超过了C的长度,矛盾。

  2. cutR为什么可以是n1,不是超过数组长度了么?

    首先要明确cutR代表了什么。cutL和cutR代表了这个cut可能出现的区间。如果cut在n1这个位置,证明A里面的全部元素都在前半段,也就是A的max小于B的min。这里我们在边界条件已经处理过了。

  3. 这里的elif可以是if么?能不能再多排除一点?

    假设这两个条件同时成立,L1>R2,L2>R1L_1\gt R_2, L_2 \gt R_1,那么R1L1>R2L2R1>L2R_1 \geq L_1 \gt R_2 \geq L_2 \Rightarrow R_1 \gt L_2L2>R1L_2 \gt R_1矛盾,所以是不可能的。