leetcode-4 求两个有序数组的中位数

题目

求两个有序数组nums1(长度为m),nums2(长度为n)的中位数
例如:
1.

1
2
3
nums1 = [1,3]
nums2 = [2]
中位数是2

2.

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

中文数是 (2 + 3)/2 = 2.5

要求,时间复杂度为O(log(m+n))

分析

最直观的解法就是将两个数组重新排序,然后根据长度,直接找出中位数,但这样做的时间复杂度至少为O(n),大于题目所要求的O(log(m+n))。
根据log(m+n)这个要求,很容易想到二分法,但具体应该怎么分呢?

思路

首先理解中位数究竟是什么,中位数就是将数组A分隔成为左右两个长度相等,右边的最小值大于左边最大值的数。假设数组A的长度为m,B的长度为n,
我们将A分隔成左右两部分:
left_A | right_A
A[0], A[1], …, A[i-1] | A[i], A[i+1], …, A[m-1]

同理将B分隔成两部分:
left_B | right_B
B[0], B[1], …, B[j-1] | B[j], B[j+1], …, B[n-1]

如果我们可以保证:

1
2
1. len(left_part) = len(right_part)
2. max(left_part) ≤ min(right_part)

那么我们就找到了中位数: median = (max(left_part) + min(right_part)) / 2

要保证上述条件,我们需要满足:

  1. i+j = m -i + n - j (或 m - i + n - j + 1) 如果 n >= m, 我们需要设置 i = 0~m,j = (m + n +1) / 2 - j
  2. A[i-1] <= B[j] 和 B[j-1] <= A[i]

否则,
如果A[i-1] > B[j],说明i的值过大,需要缩小i的值
如果B[j-1] > A[i],说明i的值过小,需要增大

解题:

  1. 遍历B数组,将B数字组中的值插入到A当中,时间复杂度大于O(n)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    def findMedian(l):
    if not l:
    return False

    if len(l) == 1:
    return l[0], 0

    q, r = divmod(len(l), 2)
    if r:
    return l[q], q
    else:
    return (l[q - 1] + l[q]) / 2, q - 1

    def get_new_sorted_arrary(l1, n):
    if not l1:
    return [n]
    mx = l1[len(l1)-1]
    mi = l1[0]
    if n > mx:
    return l1 + [n]
    if n < mi:
    return [n] + l1
    m, p = findMedian(l1)
    if m == n:
    l1.insert(p + 1, n)
    return l1
    if len(l1) == 1:
    if m < n:
    l1.insert(1, n)
    else:
    l1.insert(0, n)
    return l1
    else:
    if n > m:
    return l1[:p + 1] + get_new_sorted_arrary(l1[p + 1:], n)
    else:
    return get_new_sorted_arrary(l1[:p + 1], n) + l1[p + 1:]

    if len(nums1)>=len(nums2):
    for i in range(len(nums2)):
    nums1 = get_new_sorted_arrary(nums1, nums2[i])
    return findMedian(nums1)[0]
    else:
    for i in range(len(nums1)):
    nums2 = get_new_sorted_arrary(nums2, nums1[i])
    return findMedian(nums2)[0]
  2. 利用二分法查找,时间复杂度为O(log(m+n))

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: float
    """

    def median(A, B):
    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_len = 0, m, (m + n + 1) // 2
    while imin <= imax:
    i = (imin + imax) // 2
    j = half_len - i
    if i < m and B[j-1] > A[i]:
    # i is too small, must increase it
    imin = i + 1
    elif i > 0 and A[i-1] > B[j]:
    # i is too big, must 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

    return median(nums1,nums2)
你的支持我的动力