题目
求两个有序数组nums1(长度为m),nums2(长度为n)的中位数
例如:
1.1
2
3nums1 = [1,3]
nums2 = [2]
中位数是2
2.1
2
3
4nums1 = [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
21. len(left_part) = len(right_part)
2. max(left_part) ≤ min(right_part)
那么我们就找到了中位数: median = (max(left_part) + min(right_part)) / 2
要保证上述条件,我们需要满足:
- i+j = m -i + n - j (或 m - i + n - j + 1) 如果 n >= m, 我们需要设置 i = 0~m,j = (m + n +1) / 2 - j
- A[i-1] <= B[j] 和 B[j-1] <= A[i]
否则,
如果A[i-1] > B[j],说明i的值过大,需要缩小i的值
如果B[j-1] > A[i],说明i的值过小,需要增大
解题:
遍历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
46def 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]利用二分法查找,时间复杂度为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
42class 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)