发布于 

寻找两个有序数组的中位数

Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

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

The median is 2.0
Example 2:

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

The median is (2 + 3)/2 = 2.5

题目大意

“中位数”的作用是什么?

将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。

其中有序数组又分为:

  • 奇数组: [2 3 4] 对应的中位数为 3
  • 偶数组: [1 5 7 9] 对应的中位数为 (5 + 7) / 2 = 6

解题思路

切割数组

通过切割将有序数组分割为左右两部分, 两部分长度一致，且分割的位置，左侧为左部分最大值 MaxL=Max(LeftPart)Max_L = Max(LeftPart)

MinR=Min(RightPart)Min_R = Min(RightPart)

如上述奇数组和偶数组所示，切割的位置可以为一个数(3)，此时此数同时属于左右两部分，也可以为两个数中间, 此时取平均数。

  • 奇数组: [2 3 4] 中位数为 3，此时切割位置为数字3，将数组分为左右两部分，此时数组等同于[2 (3/3) 4]，所以 MaxL=3,MinR=3Max_L = 3, Min_R = 3
  • 偶数组: [1 5 7 9] 中位数为 6，此时切割的位置为数字5与7之间，将数组分为左右两部分，此时数组等同于[1 (5/7) 9]，所以MaxL=5,MinR=7Max_L = 5, Min_R = 7

切割第k个元素

单个数组

对于一个有序数组A，如果在位置k处切割恰好能将其分割成左右两部分长度一致的Slice(切割点落在数字上，而不是两个数之间)，那么此时 MaxL=MinR=A(k)Max_L = Min_R = A(k)

多个数组

如题所示，分别切割两个有序数组，分割出的左侧与右侧长度一致，定义切割位置为第k位的元素

SiS_i 为切割位置元素 MaxLiMax_{Li} 为左侧部分第`i`位最大元素 MinRiMin_{Ri} 为右侧部分第`i`位最小元素

MaxL<=MinR

因为数组为有序数组，所以，MaxALi<=MinARi,MaxBLi<=MinBRiMaxA_{Li} <= MinA_{Ri}, MaxB_{Li} <= MinB_{Ri}，而如果切割点在某个数上，则两边相等。

如果使得MaxALi<=MinBRi,MaxBLi<=MinBRiMaxA_{Li} <= MinB_{Ri}, MaxB_{Li} <= MinB_{Ri}

exchange

如果 LeftPart全部小于RightPart，如果左边的元素个数为 k，那么第 k 个元素为 Max(MaxLa,MaxLb)Max(Max_{La},Max_{Lb})

而如果 MaxALi>>MinBRiMaxA_{Li} >> MinB_{Ri}，则说明左侧元素远大于右侧，将 SaiS_{ai}减小，则 Sbi=k−SaiS_{bi} = k - S_{ai} 增大；相反 MaxBLi>>MinARiMaxB_{Li} >> MinA_{Ri}，将SbiS_{bi}减小，相应的Sai=k−SbiS_{ai} = k - S_{bi}也增大。

假设切割元素k=3

对于有序数组 [2 3 4]、[1 5 7 9]设Sai=1S_{ai} = 1，那么Sbi=k−Sai=2S_{bi} = k - S_{ai} = 2，即 [2 / 3 4]、[1 5 / 7 9]，此时MaxALi=2,MinARi=3;MaxA_{Li} = 2, MinA_{Ri} = 3;

MaxBLi=5,MinBRi=7;MaxB_{Li} = 5, MinB_{Ri} = 7;

此时MaxBLi>MinARiMaxB_{Li} > MinA_{Ri}，需要将SbiS_{bi}减小，SaiS_{ai}增大，让Sai=2S_{ai} = 2，此时有序数组分割为: [2 3 / 4]、[1 / 5 7 9]，此时

MaxALi=3,MinARi=4;MaxA_{Li} = 3, MinA_{Ri} = 4; MaxBLi=1,MinBRi=5;MaxB_{Li} = 1, MinB_{Ri} = 5;

满足MaxALi<MinBRiMaxA_{Li} < MinB_{Ri}且MaxBLi<MinARiMaxB_{Li} < MinA_{Ri}，所以第 k(3)个元素为Max(MaxALi,MaxBLi)=3Max(MaxA_{Li},MaxB_{Li}) = 3

转换数组

为了将数组中位数计算方式统一（计算左边最大值与右边最小值的平均值，切割点为两数之间而不是数字上），对数组进行如下填充：

元数组LenbeforeLen_{before}处理数组LenafterLen_{after}
[2 3 4]3[* 2 * 3 * 4 *]7
[1 5 7 9]4[* 1 * 5 * 7 * 9 *]9

将数组元素前后位置用*进行填充，使得原数组A长度由m变为2m+1，原数组B长度由n变为2n+1，两个数组总长度为2m+2n+2，数组总长度总是为偶数，而偶数长度数组切分方式为：两边长度一致，取左边最大值与右边最小值的平均数。

原元素位置 = 现元素位置/2 取整，；例如元素2，原索引为0，现索引为1，则 1/2=0；元素7，原索引为2，现索引为5，则 5/2=2

对于切割点SiS_i则有MaxLi=(Si−1)/2,MinRi=Si/2Max_{Li} = (S_i - 1) / 2, Min_{Ri} = S_i / 2 位置上的元素。

验证

对于数组A [2 3 4]，切割点为 3，则 Si=3S_i = 3，

MaxLi=A[(3−1)/2]=A[1]=3Max_{Li} = A[(3-1)/2] = A[1] = 3, MinRi=A[3/2]=A[1]=3Min_{Ri} = A[3/2] = A[1] = 3

对于数组B [1 5 7 9]， 切割点在数字 5与7之间的*，则 Si=4S_i = 4，

MaxLi=B[(4−1)/2]=A[1]=5Max_{Li} = B[(4-1)/2] = A[1] = 5, MinRi=B[4/2]=A[2]=7Min_{Ri} = B[4/2] = A[2] = 7

将两个数组看作一个整体S，则数组总长度为 2m+2n+2，切割点为 m+n+1，所以计算 m+n+1以及m+n+2元素就可以得到中位数。

左侧部分：S[m+n+1]=Max(MaxALi,MaxBLi)S[m+n+1] = Max(MaxA_{Li},MaxB_{Li})

右侧部分：S[m+n+2]=Min(MinARi,MinBRi)S[m+n+2] = Min(MinA_{Ri},MinB_{Ri})

中位数：Smid=(S[m+n+1]+S[m+n+2])/2=(Max(MaxALi,MaxBLi)+Min(MinARi,MinBRi))/2S_{mid} = (S[m+n+1] + S[m+n+2])/2 = (Max(MaxA_{Li},MaxB_{Li}) + Min(MinA_{Ri},MinB_{Ri}))/2

综合

使用二分法对长度较短的数组进行切分，得到 SaiS_{ai} 则 SbiS_{bi} 也确定了。

  • MaxALi>MinBRiMaxA_{Li} > MinB_{Ri}，则 SaiS_{ai} 减小，SbiS_{bi} 增大，切割点在数组`A`左移进行二分
  • MaxBLi>MinARiMaxB_{Li} > MinA_{Ri}，则 SaiS_{ai} 增大，SbiS_{bi} 减小，切割点在数组`A`右移进行二分

如果有个数组完全小于或大于中值，此时 n < m，出现以下几种情况：

  • Sai=0S_{ai} = 0 ，此时数组元素全部在右侧部分，Sbi=k−SaiS_{bi} = k - S_{ai} 存在与数组 `B`中，假设 MaxALiMaxA_{Li} = `INT_MIN`
  • Sai=2mS_{ai} = 2m，此时数组元素全部在左侧部分，Sbi=k−SaiS_{bi} = k - S_{ai} 存在与数组 `B`中，假设 MinALiMinA_{Li} = `INT_MAX`，此时 MaxBLi<<MinARiMaxB_{Li} << MinA_{Ri}
  • Sbi=0S_{bi} = 0 ，此时数组元素全部在右侧部分，Sai=k−SbiS_{ai} = k - S_{bi} 存在与数组 `A`中，假设 MaxBLiMaxB_{Li} = `INT_MIN`
  • Sbi=2nS_{bi} = 2n，此时数组元素全部在左侧部分，Sai=k−SbiS_{ai} = k - S_{bi} 存在与数组 `A`中，假设 MinBRiMinB_{Ri} = `INT_MAX`，此时 MaxALi<<MinBRiMaxA_{Li} << MinB_{Ri}

代码

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
64
65
66
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    var m, n = len(nums1), len(nums2)
    if m > n { // 确保nums1长度较短
        return findMedianSortedArrays(nums2, nums1)
    }
    
    const (
        INT_MAX = int(^uint(0) >> 1)
        INT_MIN = ^INT_MAX
    )
    
    // S1,S2为切割点索引
    var MaxLA, MaxLB, MinRA, MinRB, S1, S2, lop int
    var hi = 2 * m + 1 //数组A补全*, 长度变为 2m+1
    for lop <= hi {
        S1 = (lop + hi) / 2;
        S2 = m + n - S1;
        
        if S1 == 0 {
            MaxLA = INT_MIN
        } else {
            MaxLA = nums1[(S1 - 1) / 2]
        }
        
        if S1 == 2 * m {
            MinRA = INT_MAX
        } else {
            MinRA = nums1[S1 / 2]
        }
        
        if S2 == 0 {
            MaxLB = INT_MIN
        } else {
            MaxLB = nums2[(S2 - 1) / 2]
        }
        
        if S2 == 2 * n {
            MinRB = INT_MAX
        } else {
            MinRB = nums2[S2 / 2]
        }

        if MaxLA > MinRB {
            hi = S1 - 1
        } else if MaxLB > MinRA {
            lop = S1 + 1
        } else {
            break
        }
    }
    return float64(max(MaxLA, MaxLB) + min(MinRA, MinRB)) / 2.0
}

func max(a,b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a,b int) int {
    if a > b {
        return b
    }
    return a
}

思路参考 bian-bian-xiong题解

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章
快来参与讨论吧