Leetcode No.4 两个排序数组的中位数/Median of Two Sorted Arrays

分手后的思念是犯贱 2022-05-17 05:21 189阅读 0赞

# 问题描述： #

给定两个大小为 m 和 n 的有序数组 **nums1 **和 **nums2 **。

请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。

你可以假设 **nums1** 和 **nums2** 均不为空

## **示例：** ##

nums1 = [1, 2]
    nums2 = [3, 4]
    
    中位数是 (2 + 3)/2 = 2.5

# 思路与分析： #

## 1.直接合并： ##

### 思路： ###

用归并排序的思路合并两个有序数组，直接求中位数

### 时间复杂度： ###

只需扫描一遍两个数组，复杂度是O(m+n)

笔者尝试着提交了这份code发现可以通过= =

虽然已经足够快了，但还是达不到题目要求的对数时间复杂度O(log(m+n))，所以要换一种思路

## 2.Binary Search ##

### 思路： ###

由对数时间的复杂度很容易联想到树的查找与二分查找

（1）如果使用二叉树来做

首先要build binary tree，这个过程中每次insert需要O(log(n+m))的时间，把 n + m 个元素放到树上需要O((n+m)log(n+m))的时间，已经超时了= =

（2）二分查找

本题思路非常巧妙，LeetCode上已有详尽解答，我在这里记录下个人的理解。

我们的目的是求出中位数，从中位数的定义出发，它将一个序列切成等长的两半，而且左半边的任意元素一定小于右半边的任意元素。

求一个有序数组的中位数，直接取中即可；

求两个有序数组A，B的中位数，用同样的思路，找两个分界点 i 和 j， 分别把A， B切开，

我们得到四段有序数组：**A\_left, A\_right, B\_left, B\_right**

把 A\_left 和 B\_left 放在一起叫 left\_part，把 A\_right 和 B\_right 放在一起叫 right\_part

假如 left\_part 和 right\_part 长度相等，而且 **max(left\_part) <= min(right\_part)**，就表明我们成功地将集合\{A, B\}的元素分成等长

的两半，而且左半边的任意元素一定小于右半边的任意元素，满足了中位数的定义，此时

**median = ( max(left\_part) + min(right\_part) )/2**

翻译一下这两个条件：

（1）left\_part 和 right\_part 长度相等 ——> **i + j = m - i + n - j + 1**，即 **j = (n+m+1)/2 - i **

**     **(2）max(left\_part) <= min(right\_part) ——> **A\[i - 1\] <= B\[ j \]** and **B\[j - 1\] <= A\[ i \]**

\#数组A和B的长度分别为m,n

换言之，我们要找到一个 **i **， 使得以下式子成立：**A\[i - 1\] <= B\[ j \]** and **B\[j - 1\] <= A\[ i \]，**其中 **j = (n+m+1)/2 - i**

由于m、n已知，**j **是由 **i 唯一确定**的，只要找到这个 **i ，**我们就收工了：）

目标转换成在有序数组A中查找一个符合要求的元素 **A\[ i \]**，现在的任务是查找！

在有序数组中查找元素，毫无疑问就是二分查找了

用 **imin **,**imax **标记查找的边界，初始时 **imin = 0**， **imax = m**

对于二分查找，无非会遇到三种情况：

（1）**i **是完美的：**A\[i - 1\] <= B\[ j \]** and **B\[j - 1\] <= A\[ i \]**，done√

（2）**i **偏小，意味着 **B\[j - 1\] > A\[ i \]**，调整边界到 **i** 的右侧查找：**imin = i+1**

（3）**i **偏大，意味着 **A\[i - 1\] > B\[ j \]**，调整边界到 **i** 的左侧查找：**imax = i - 1**

查找过程中还会遇到一些边界情况：**i = 0, m** 以及 **j = 0, n**，这个看官方解答很容易理解，不再赘述

### 时间复杂度： ###

**O(log(n+m))**

# 代码实现（Python）: #

class Solution:  
    def findMedianSortedArrays(self, nums1, nums2):  
        """  
        :type nums1: List\[int\]  
        :type nums2: List\[int\]  
        :rtype: float  
        """  
        A, B = nums1, nums2  
        m, n = len(A), len(B)  
        if m > n:  
            A, B, m, n = B, A, n, m  
        if n == 0:  
            raise ValueError  
        imin, imax, half\_of\_len = 0, m, (n+m+1)/2  
        while imin <= imax:  
            i = (imin+imax)/2  
            j = half\_of\_len - i  
            if i < m and A\[i\] < B\[j-1\]:  
                \# i is too small, increase it  
                imin = i + 1  
            elif i > 0 and B \[ j \] < A\[i-1\]:  
                \# i is too big, decrease it  
                imax = i - 1  
            else:  
                \# i is perfect  
                if i == 0:    max\_of\_left = B\[j-1\]  
                elif j == 0:    max\_of\_left = A\[i-1\]  
                else:     max\_of\_left = max(A\[i-1\], B\[j-1\])

if (m+n)%2 == 1:  
                    return max\_of\_left

if i == m:    min\_of\_right = B\[j\]  
                elif j == n:    min\_of\_right = A\[i\]  
                else:    min\_of\_right = min(A\[i\], B\[j\])

return (max\_of\_left+min\_of\_right)/2.0

# Reference #

[https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/][https_leetcode-cn.com_problems_median-of-two-sorted-arrays_solution]

[https_leetcode-cn.com_problems_median-of-two-sorted-arrays_solution]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/