找出两个有序数组的整体中位数 , 输入： 两个有序数列 , 输出： 总体数列的中位数
输入: {1, 2, 7, 10, 11, 12, 23} ， {3, 5, 8, 9, 22}
输出: 8.5
方法一
在上面题目中很容易想到方法是， 将两个有序数组合并成一个数组，然后长度除以2, 得到中间数字就是中位数
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
| package main
func MiddleNumber(a, b []int) float32 {
tmp := make([]int, len(a)+len(b))
for i, ai, bi := 0, 0, 0; i < len(tmp); i++ {
if ai < len(a) && bi < len(b) {
if a[ai] < b[bi] {
tmp[i] = a[ai]
ai++
} else {
tmp[i] = b[bi]
bi++
}
} else {
if ai < len(a) {
tmp[i] = a[ai]
ai++
} else {
tmp[i] = b[bi]
bi++
}
}
}
if len(tmp)%2 == 1 {
return float32(tmp[len(tmp)/2])
} else {
return float32(tmp[len(tmp)/2]+tmp[len(tmp)/2-1]) / 2.0
}
}
func main() {
a := []int{1, 2, 7, 10, 11, 12, 23}
b := []int{3, 5, 8, 9, 22}
m := MiddleNumber(a, b)
fmt.Println("middle number:", m)
}
|
上面这种算法能够很好的解决问题， 也很好理解，但是效率不是特别好， 时间复杂度为O(A+B)。
在面试中往往会要求你使用最优解来解决问题，上面的方法就不会很好使了。。。
方法二
请仔细观察下图：
中位数将合并好的数组分为左右部分，左右部分分别有数组A,B两个数组的左右部分组成，我们只要找到分割数组AB的位置就可以很容易计算出中位数
观察可以得到如下关系 Ma + Mb = (len(a) + len(b) + 1) / 2
基数数组中位数 max(a[Ma-1], b[Mb-1])
偶数数组中位数 (max(a[Ma-1], b[Mb-1]) + min(a[Ma], b[Mb]))/2
并且左右两部分需要满足：
a[Ma] >= b[Mb-1] && b[Mb]>=a[Ma-1]
如果出现a[Ma] < b[Mb-1]， 说明现在A的分界点太大，需要向右移动
如果出现b[Mb] < a[Ma-1],，说明现在A的分界点太小，需要向右移动
B的分解点可以计算得出 Mb = (len(a) + len(b) + 1) / 2 - Ma
由于原始数组是有序数组，我们可以使用二分法来选择A的分解点
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
| package main
func MiddleNumber(a, b []int) float32 {
if len(a) < len(b) {
return MiddleNumber(b, a)
}
ma, mb := 0, 0
la, ra := 0, len(a)
ms := (len(a) + len(b) + 1) / 2
for la < ra {
ma = (ra-la)/2 + la
mb = ms - ma
if b[mb-1] > a[ma] {
ra = ma
} else if b[mb] < a[ma-1] {
la = ma
} else {
break
}
}
if (len(a)+len(b))%2 != 0 {
if a[ma-1] > b[mb-1] {
return float32(a[ma-1])
} else {
return float32(b[mb-1])
}
} else {
return float32(maxInt(a[ma-1], b[mb-1])+minInt(a[ma], b[mb])) / 2.0
}
}
func main() {
a := []int{1, 2, 7, 10, 11, 12, 23}
b := []int{3, 5, 8, 9, 22}
m := MiddleNumber(a, b)
fmt.Println("middle number:", m)
}
|
使用上面算法可以做到时间复杂度为O(lg(min(A, B)))