面试中算法（找到两个数组的中位数）

布满荆棘的人生 2024-05-28 10:22 89阅读 0赞

#### 有两个升序数组，如何找出这两个数组归并以后新的升序数组的中位数? ####

> 中位数把一个升序数组分成了长度相等的两部分，其中左半部分的最大值永远小于或等于右半部分的最小值。

![6c32c45660da4202b2129d8aa0f48666.png][]

![8464a504029549bd8451bd8953a27443.png][]

> 如上图所示，对于**偶数**长度的数组，可以根据**中位数**分成长度相等的两部分，左半部分的最大元素（6），永远小于或等于右半部分的最小元素(7)。

![d46bcd50608742be9870de16fb2ef829.png][]

![ec8481bed08649ea9c829cd6659bb367.png][]

> 如上图所示，对于**奇数**长度的数组，如果把**中位数**本身归入左半部分，则左半边长度=右半边长度+1。 左半部分的最大元素（5），永远小于或等于右半部分的最小元素（6）。

![53f5a29757e440b081b96ce6a0a3392b.png][]

> 假设：
> 
> 数组A的长度是m，绿色和橙色元素的分界点是i，
> 
> 数组B的长度是n，绿色和橙色元素的分界点是j，
> 
> 那么为了让大数组的左右两部分长度相等，则i和j需要符合如下两个条件:
> 
> i+j= (m+n+1)/2 (之所以m+n后面+1，是为了应对大数组长度为奇数情况。)
> 
> Max(A\[i-1\],Blj-1\])<= Min(A\[i\], B\[j\])(就是最大的绿色元素小于或等于最小的橙色元素。)
> 
> 由于m+n的值是恒定的，所以我们只要确定一个合适的i，就可以确定j，从而找到大数组左半部分和右半部分的分界，也就找到了归并之后大数组的中位数。
> 
> 其中i可以利用“二分查找”的思想。

如下图所示：

**第一步**：就如二分查找那样，把i设在数组A的正中位置 i=3:

![a44bf24eff9242d28ab6b638a38d0934.png][]

**第二步：**根据i的值来确定j的值，j= (m+n+1）/2 -i = 5:

![bc24a27649d34cb5b1067bc5f2078444.png][]

**第三步： 验证i和j，分为下面三种情况:**

> 1、B\[j-1\]≤A\[i\]&& A\[i-1\]≤B\[j\] 说明i和j左侧的元素都小于或等于右侧的元素。
> 
> 2、A\[i\]<B\[j-1\] 说明i对应的元素偏小了，i应该向右侧移动。
> 
> 3、A\[i-1\]>B\[j\] 说明i-1对应的元素偏大了，i应该向左侧移动。
> 
> **显然，图中的属于情况2，A\[3\]< B\[5\]，所以i应该向右移动。**

**第四步：**在数组A的右半部分，重新确定i的位置，就像二分查找一样:

![1752e8ad534b48c796bec7fdffaf45ad.png][]

**第五步**：同第二步，根据i的值来确定j的值，j= (m+n+1）/2-i = 3:

![a6252b69ac9840bd8e12525bb678d757.png][]

**第六步**：同第三步，验证i和j: 由于A\[5\] >=B\[2\]且B\[3\]>=A\[4\]，所以这一组i和j是合适的!

**第七步**：找出中位数:

如果大数组的长度是**奇数**，

中位数= Max (A\[i-1\]，B\[j-1\]>） (大数组左半部分的最大值。)

如果大数组的长度是**偶数**，

中位数= (Max (A\[i-1\]，B\[j-1\]) +Min（A\[i\]，B\[i\]))/2

(大数组左半部分的最大值和大数组右半部分的最小值取平均。)

> 在图示：大数组的长度是奇数，所以中位数=Max (8，12）=12。

#### 特殊情况： ####

**1、数组A的长度远大于数组B**

![6caf15df4ced4f6380afa278659fd67c.png][]

可以提前把数组A和数组B进行交换，较短的数组放在前面，i从较短的数组中取。由于数组A是较短数组，i的搜索次数减少了。

**2、无法找到合适的i值**

**（1）数组A的长度<数组B的长度，并且数组A的所有元素都>数组B的元素。**

![1c3153c6a8fc47ba9b7efcad054e7e3f.png][]

可以跳出二分查找的循环，所求的中位数是B\[j-1\]。（仅限奇数情况)

**（2）数组A的长度<数组B的长度，并且数组A的所有元素都<数组B的元素。**

![03b6047dae744cdabbdcdcf0eaacbdf0.png][]

可以跳出二分查找的循环，所求的中位数是Max (A\[i-1\]，B\[j-1\])。(仅限奇数情况)

def get_middle_number(arrA,arrB):
        #获取数组的大小
        m,n=len(arrA),len(arrB)
        #判断arrA大小>=arrB大小,则交换
        if m>n:
            arrA,arrB, m,n,=arrB,arrA,n,m
        #如果n为0,值异常
        if n==0:
            raise  ValueError
        #起点，终点，中间
        start,end,half=0,m,(m+n+1)//2
        #循环
        while start<=end:
            i=(start+end)//2
            j=half-i
            # 验证i和j，三种情况
            if i<m and arrB[j-1]>arrA[i]:
                #(1) i偏小了，需要右移
                start=i+1
            elif i>0 and arrA[i-1]>arrB[j]:
                #(2) i偏大了，需要左移
                end=i-1
            else:
                #(3) i刚好合适，或i已达到数组边界
                if i == 0:
                    max_of_left = arrB[j - 1]
                elif j == 0:
                    max_of_left = arrA[i - 1]
                else:
                    max_of_left = max(arrA[i - 1], arrB[j - 1])
                if (m + n) % 2 == 1:
                    # 如果大数组的长度是奇数，中位数就是左半部分的最大值
                    return max_of_left
                if i == m:
                    min_of_right = arrB[j]
                elif j == n:
                    min_of_right = arrA[i]
                else:
                    min_of_right = min(arrA[i], arrB[j])
                # 如果大数组的长度是偶数，取左侧最大值和右侧最小值的平均
                return (max_of_left + min_of_right) / 2.0
    
    if __name__ == '__main__':
        arrA = list([3, 5, 6, 7, 8, 15, 20])
        arrB = list([1, 10, 12, 18,21,24,25,29])
        print(get_middle_number(arrA,arrB))

![b5d0d195afbd498cb6a1960b325f2c03.png][]

[6c32c45660da4202b2129d8aa0f48666.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/847abca44bcb426fb6277b4f48187e3c.png
[8464a504029549bd8451bd8953a27443.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/4a1e44f6bb3c48d9bfdc6ddb3c7b8a54.png
[d46bcd50608742be9870de16fb2ef829.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/3827a70d6ea547b4a3ebfb04e0c68012.png
[ec8481bed08649ea9c829cd6659bb367.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/5608fa5aa03344c8af8d611ffc3975b5.png
[53f5a29757e440b081b96ce6a0a3392b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/7eceeea2aa84404eb64e8178d506d2f5.png
[a44bf24eff9242d28ab6b638a38d0934.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/16c00fb50ac646efb46abc68b533d9ec.png
[bc24a27649d34cb5b1067bc5f2078444.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/dcd1deddc40740e8a438bad6f0fdc2b7.png
[1752e8ad534b48c796bec7fdffaf45ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/5ce927585888463282a4ba0fc63db5a4.png
[a6252b69ac9840bd8e12525bb678d757.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/566730fef96246a0b3450973f5cb4c20.png
[6caf15df4ced4f6380afa278659fd67c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/9cd5c8932c86411eb58cb7a87fe39962.png
[1c3153c6a8fc47ba9b7efcad054e7e3f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/1b6aac3af53948899b2070f7be139410.png
[03b6047dae744cdabbdcdcf0eaacbdf0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/32b53eeadbbc4f579f6337f067c10ce0.png
[b5d0d195afbd498cb6a1960b325f2c03.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/b1dbd29dc44d4a5992e2a2788cd873c3.png