leetcode 两个正序数组的中位数
题目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.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
| class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
if len(nums1) < len(nums2):
nums1, nums2 = nums2, nums1
index1 = 0
index2 = 0
total = len(nums1) + len(nums2)
while index2 < len(nums2) and index1 <= total / 2:
if index1 < len(nums1):
if nums1[index1] > nums2[index2]:
nums1.insert(index1, nums2[index2])
index2 += 1
else:
index1 += 1
else:
nums1.append(nums2[index2])
index2 += 1
if total % 2 == 0:
return (nums1[int(total / 2) - 1] + nums1[int(total / 2)]) / 2.0
else:
return nums1[total / 2]
|
新的思路
我们这个算法时间复杂度是 O(m+n) ,题目有个要求 算法时间复杂度 O(log(m + n))，倘若没这个要求 上面的算法就可以完成了，但是有复杂度 并且是log的，这个时候我们可以想起是二分查找。
先来理解一下， 两个有序数组，中位数 可以理解寻找两个数据的第n/2+1大的数（奇数个数）或者第n/2与n/2+1个大的数的平均值。
我们思考，既然是二分查找，思路应该是第一次二分排除掉一部分 然后继续找。
假设 两个数组A与B， 要找第k大的数， 我们可以比较 A[k/2-1]与B[k/2-1] ，为啥？
因为 A与B数组前面各有 k/2-2个数 ，比较他俩 有几种情况：
这说明A[k/2-1] 前面那个数(也就是A[k/2-2]) 要么等于A[k/2-1]要么大于A[k/2-1] (因为A有序) ，再来看A[k/2-2]与B数组的关系， 他与B[k/2-1] 的关系，也就是如果合并，A[k/2-2]一定是在B[k/2-1]这个数后面，也就是说A[k/2-2]前面有 B[k/2-1]这个数前面的所有数 有k/2-1个+A数组前面 k/2-2 = k-3个数，这第k个数 一定是在 B[k/2] ~ B[n] 与 A[0] ~ A[m]之间 这个时候可以把 B[k/2] ~ B[n] 看称一个新的数组， A[0] ~ A[m]看成另一个数组，这个时候k已经变成了k-(k/2-1)了， 也就是新的两个数组的k-(k/2-1)大的数， 第继续比较 两个数组的 k/2-1个数，如此循环。
这个时候跟上面的情况相反，只需要间隔A折半 A[k/2] ~A[m] 与 B[0] ~ B[n]
相等的情况， 前面有k-4个数 他俩一个是 k-3 一个是k-2 没找到第k个数 还是要找，肯定是在A[k/2] ~ A[m] 与 B[k/2] ~ B[n] 这里可以按照跟情况一或者情况二处理都一样的，都是往后移动一个。
这就是二分法查找，每次排除数组一半的数据.
举个例子两个数组：
长度 13/2+1 =7 要找到第7大的数就可以
1
2
| A: 1 3 4 9
B: 1 2 3 4 5 6 7 8 9
|
第一次 比较 A[7/2-1] ? B[7/2-1]
1
2
| A: 1 3 <4> 9
B: 1 2 <3> 4 5 6 7 8 9
|
之后数组变为以下结果，变为查找第 7 - 3 = 4大的数
1
2
| A: 1 3 4 9
B: 4 5 6 7 8 9
|
重新比较 A[4/2-1] ? B[4/2-1]
1
2
| A: 1 <3> 4 9
B: 4 <5> 6 7 8 9
|
出现相等了，只要改一个就可以, 查找 4 - 2 = 2大的数
比较 A[2/2-1] ? B[2/2-1]
1
2
| A: <4> 9
B: <4> 5 6 7 8 9
|
相等的场景，可以任意一个，这里就选择移动A数组了, 2 - 1 = 1 大的数
这里已经是第1大的数了 就是最小的那个了，直接比较A[1/2-1] ? B[1/2-1] ===> A[0] ? B[0]
这里找到了 B[0]即 4
假如这个这里找的不是第7大，而是第八大,这里要继续找继续下一组数组就是
找到了5.
代码实现
这种场景很容易想到 用递归的方式来处理
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
| func FindK(a []int, b[]int, k int) int {
if len(a) == 0 {
return b[k-1]
}
if len(b) == 0 {
return a[k-1]
}
if k == 1 {
return min(a[0],b[0])
}
index := k / 2 - 1
if index < 0 {
index = 0
}
newIndexA := min(index, len(a)-1)
newIndexB := min(index, len(b)-1)
if a[newIndexA] > b[newIndexB] {
newIndexB += 1
return FindK(a, b[newIndexB:], k-newIndexB)
} else {
newIndexA += 1
return FindK(a[newIndexA:], b, k-newIndexA)
}
}
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
total := len(nums1) + len(nums2)
if total % 2 > 0 {
r := FindK(nums1, nums2, total/2+1)
return float64(r)
}
index := total / 2
a := FindK(nums1, nums2, index)
b := FindK(nums1, nums2, index+1)
return float64(a + b) / 2
}
|
再来看下非递归的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func FindK(a []int, b[]int, k int) int {
indexA, indexB := 0,0
for {
if indexA >= len(a) || len(a) == 0 {
return b[indexB+k-1]
}
if indexB >= len(b) || len(b) == 0 {
return a[indexA+k-1]
}
if k == 1 {
return min(a[indexA], b[indexB])
}
newIndexB := min(indexB+k/2-1, len(b)-1)
newIndexA := min(indexA+k/2-1, len(a)-1)
if a[newIndexA] > b[newIndexB] {
k = k - (newIndexB-indexB+1)
indexB = newIndexB + 1
} else {
k = k - (newIndexA - indexA+1)
indexA = newIndexA + 1
}
}
}
|
终于，花了两个晚上 弄懂了以上一个非常简单的算法，深感智商有限，你的努力在天赋面前不值一提，你努力达到的高度，可能是别人的起点。
平凡人的努力，终究是徒劳。