在两个排序数组中找到上中位数

给定两个有序数组 arr1 和 arr2 ，已知两个数组的长度都为 N，求两个数组中所有数的上中位数。

【举例】

arr1 = [ 1, 2, 3, 4 ] ， arr2 = [ 3, 4, 5, 6 ]

总共有 8 个数，那么上中位数是第 4 小的数，所以返回 3

arr1 = [ 0, 2, 3 ] ， arr2 = [ 3, 4, 5]

总共有 6 个数，那么上中位数是第 3 小的数，所以返回 2

【要求】

时间复杂度为 O( log N )，额外空间复杂度 O(1)

方案一

N 为偶数

比较 arr1 和 arr2 的中位数 median1 = c 和 median2 = i 。

如果 c == i，那么 c 和 i 就是 Top K，直接返回。

假设 c > i 。那么 [ d, e, f ] > [ a , b , g, h, i , c ] , 所以 [ d, e, f ] 中不可能为 Top 6。[ g, h, i ] < [ c, d, e, f, j, l, m ] 那么 [ g, h, i ] 不可能为 Top 6。因此可以将 arr1 中的 [ d, e, f ] 删除后获取 arr1 = [ a, b, c ] , 将 arr2 中 [ g, h, i ] 删除，获取 arr2 = [ j, l, m ]。

继续对 arr1 = [ a, b, c ] 和 arr2 = [ j, l, m ] 求解。

N 为奇数

• 如果 c == i，那么 c 和 i 就是 Top K，直接返回。

比较 arr1 和 arr2 的中位数 median1 = c 和 median2 = i 。假设 c > i 。那么 c > [ a , b , g, h, i ] , 所以 [ c, d, e, f ] 中不可能为 Top 5。[ g, h ] < [ c, d, e, i, j, l] 那么 [ g, h ] 不可能为 Top 5。因此可以将 arr1 中的 [ c, d, e ] 删除后获取 arr1 = [ a, b ] , 将 arr2 中 [ g, h ] 删除，获取 arr2 = [ i, j, l ]。

此时 arr1 和 arr2 长度不相同了，没有办法求解子问题了。

因此：我们可以手动尝试比较 b 和 i，

• 如果 i > b，那么 i > [ a, b, g, h ]，此时 i 就是 Top 5 直接返回。

• 如果 i < b， i < [ c, d, e, i, j, l ] ，i 不可能为 Top 5，可以删除。
  

def get_up_median(arr1, arr2):
    if len(arr1) != len(arr2): return
    return process(arr1, 0, len(arr1) - 1, arr2, 0, len(arr2) - 1)

def process(arr1, left1, right1, arr2, left2, right2):
    if left1 == right1 and left2 == right2:
        return min(arr1[left1], arr2[left2])

    mid1 = int((right1 - left1) / 2) + left1
    mid2 = int((right2 - left2) / 2) + left2
    if arr1[mid1] == arr2[mid2]: return arr1[mid1]
    # 数组长度为偶数
    if (right1 - left1) % 2 == 1 and (right2 - left2) % 2 == 1:
        if arr1[mid1] > arr2[mid2]:
            return process(arr1, left1, mid1, arr2, mid2 + 1, right2)
        else:
            return process(arr1, mid1 + 1, right1, arr2, left2, mid2)
    # 奇数
    else:
        if arr1[mid1] > arr2[mid2]:
            if arr1[mid1 - 1] < arr2[mid2]: return arr2[mid2]
            return process(arr1, left1, max(mid1 - 1, 0), arr2, mid2 + 1, right2)
        else:
            if arr2[mid2 - 1] < arr1[mid1]: return arr1[mid1]
            return process(arr1, mid1 + 1, right1, arr2, left2, max(mid2 - 1, 0))


def get_up_median2(arr1, arr2):
    if len(arr1) != len(arr2): return

    data = []

    for item in arr1:
        data.append(item)

    for item in arr2:
        data.append(item)
    mid = int(len(data) / 2) - 1
    data = sorted(data)
    return data[mid]

# 对数器
import random

def generator(size, max_value):
    return [int(random.random() * max_value) + 1 for _ in range(size)]

def check():
    max_value = 10
    max_size = 10
    n = 100

    for i in range(n):
        size = int(random.random() * max_size) + 1
        arr1 = sorted(generator(size, max_value))
        arr2 = sorted(generator(size, max_value))
        expect = get_up_median(arr1[:], arr2[:])
        actual = get_up_median2(arr1[:], arr2[:])
        if expect != actual:
            print("ERROR", arr2, arr1, actual, expect)
    print("Over!")

check()
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

方案二

上边通过递归实现的。其实在查找过程中，只是 left ，right 指针在不同情况下，有不同的偏移量。我们只需要将offset 计算对，即可。

在奇数时，为了避免出现arr1 和 arr2 两个子数组长度不一致，长度短的数组每次少减一个，留给下一次处理去丢弃该数据。

def get_up_median3(arr1, arr2):
    if not arr1 or not arr2 or len(arr1) != len(arr2): return

    left1 = left2 = 0
    right1 = right2 = len(arr1) - 1
    while left1 < right1:
        mid1 = int((left1 + right1) / 2)
        mid2 = int((left2 + right2) / 2)

        if arr1[mid1] == arr2[mid2]:
            return arr1[mid1]

        # 元素个数为奇数，offset = 0；元素个数为偶数：offset = 1
        offset = 1 if (right1 - left1) % 2 == 1 else 0
        if arr1[mid1] > arr2[mid2]:
            right1 = mid1
            left2 = mid2 + offset
        else:
            left1 = mid1 + offset
            right2 = mid2

    return min(arr1[left1], arr2[left2])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22