题解 | #多数组中位数#

多数组中位数

http://www.nowcoder.com/practice/b6bb0bce88894108bfc23e9b7b012420

题目分析

题目给出了我们两个递增数组

题目要求我们返回两个数组中所有数字的中位数

方法一：双指针归并

实现思路
- 由于我们知道两个数组是升序的，我们用双指针的方式对两个表进行遍历
- 比较两个指针所指数字的大小选择是否要移动指针，进行不断迭代
- 直到两个指针所指数字某一个指针率先达到了中位数目标位置，则返回最终的数字

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param arr1 int整型一维数组 
# @param arr2 int整型一维数组 
# @return int整型
#
class Solution:
    def getUpMedian(self , arr1: List[int], arr2: List[int]) -> int:
        # write code here
        k = int((len(arr1)+len(arr2))/2)
        i, idx1, idx2 = 0, -1, -1
        f1, f2 = 0, 0
        while i < k:
            if idx1+1 < len(arr1) and idx2+1 < len(arr2):        # 两列表都未越界
                if arr1[idx1+1] < arr2[idx2+1]:                  # 比较哪一个小，哪一个下标移动
                    idx1 += 1
                    f1, f2 = 1, 0
                else:
                    idx2 += 1
                    f1, f2 = 0, 1
            elif idx1+1 < len(arr1):                             # 只有列表1未越界
                idx1 += 1
                f1, f2 = 1, 0
            else:                                                # 只有列表2未越界
                idx2 += 1
                f1, f2 = 0, 1
            i += 1
        if f1:
            return arr1[idx1]
        else:
            return arr2[idx2]

复杂度分析

时间复杂度： $O (l 1 + l 2)$ ，其中 $l 1$ 是 $a r r 1$ 的长度， $l 2$ 是 $a r r 2$ 的长度，由于遍历只有一趟，因此时间代价和长度之和成线性关系
空间复杂度： $O (1)$ ，只引入常量级别的空间开销

方法二：二分法

实现思路
- 假设两个有序数组分别是 $\text{A}$ 和 $\text{B}$ 。要找到第 $k$ 个元素，我们可以比较 $\text{A}[k/2-1]$ 和 $\text{B}[k/2-1]$ ，其中 $/$ 表示整数除法。由于 $\text{A}[k/2-1]$ 和 $\text{B}[k/2-1]$ 的前面分别有 $\text{A}[0\,..\,k/2-2]$ 和 $\text{B}[0\,..\,k/2-2]$ ，即 $k / 2 - 1$ 个元素，对于 $\text{A}[k/2-1]$ 和 $\text{B}[k/2-1]$ 中的较小值，最多只会有 $(k/2-1)+(k/2-1) \leq k-2$ 个元素比它小，那么它就不能是第 $k$ 小的数了。
- 因此我们可以归纳出2种情况：
  - 如果 $\text{A}[k/2-1] \le \text{B}[k/2-1]$ ，则比 $\text{A}[k/2-1]$ 小的数最多只有 $\text{A}$ 的前 $k / 2 - 1$ 个数和 $\text{B}$ 的前 $k / 2 - 1$ 个数，即比 $\text{A}[k/2-1]$ 小的数最多只有 $k - 2$ 个，因此 $\text{A}[k/2-1]$ 不可能是第 $k$ 个数， $\text{A}[0]$ 到 $\text{A}[k/2-1]$ 也都不可能是第 $k$ 个数，可以全部排除。
  - 如果 $\text{A}[k/2-1] > \text{B}[k/2-1]$ ，则可以排除 $\text{B}[0]$ 到 $\text{B}[k/2-1]$ 。
- 比较 $\text{A}[k/2-1]$ 和 $\text{B}[k/2-1]$ 之后，可以排除 $k / 2$ 个不可能是第 $k$ 小的数，查找范围缩小了一半。如果 $\text{A}[k/2-1]$ 和 $\text{B}[k/2-1]$ 越界，则 $k$ 减小时要根据排除的数字数量减小。同时，我们将在排除后的新数组上继续进行二分查找，并且根据我们排除数的个数，减少 $k$ 的值，这是因为我们排除的数都不大于第 $k$ 小的数。
- 如果一个数组已经为空，则直接返回另一个数组的第 $k$ 小的数字
- 如果 $k = 1$ ,直接返回两个数组首位的较小的元素即可

alt

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param arr1 int整型一维数组 
# @param arr2 int整型一维数组 
# @return int整型
#
class Solution:
    def getUpMedian(self , arr1: List[int], arr2: List[int]) -> int:
        # write code here
        def getKth(k):
            idx1, idx2 = 0, 0
            while True:
                if idx1 == m:                                    # arr1 全部被排除
                    return arr2[idx2 + k -1]
                if idx2 == n:                                    # arr2 全部被排除
                    return arr1[idx1 + k -1]
                if k == 1:                                       # k减少到1的情况
                    return min(arr1[idx1], arr2[idx2])
                nidx1 = min(m - 1, idx1 + k // 2 - 1)            # 进行下一次二分
                nidx2 = min(n - 1, idx2 + k // 2 - 1)            # 进行下一次二分
                pivot1, pivot2 = arr1[nidx1], arr2[nidx2]
                if pivot1 <= pivot2:
                    k -= nidx1 - idx1 + 1
                    idx1 = nidx1 + 1
                else:
                    k -= nidx2 - idx2 + 1
                    idx2 = nidx2 + 1
        m, n = len(arr1), len(arr2)
        if (m + n) % 2 == 1:
            return getKth((m + n + 1) // 2)
        else:
            return getKth((m + n) // 2)