题目
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
1
2
3
4
| nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
|
示例 2:
1
2
3
4
| nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
|
解法
由于指定了时间复杂度，所以不能采用普通的排序算法。
遍历
同时遍历两个数组，然后比对每一个取出的数，小的则加入到结果数组中，同时索引往后+1，继续取数比较，直到其中一个数组遍历结束，则将未结束的部分加到结果数组中。然后取中位数。
时间复杂度：$O(m,n)=min(m, n)$空间复杂度：$O(m,n)=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
| class Solution:
def findMedianSortedArrays(self, nums1, nums2) -> float:
idx1 = 0
idx2 = 0
tmpL = []
while idx1 < len(nums1) or idx2 < len(nums2):
if idx1 < len(nums1):
num1 = nums1[idx1]
else:
tmpL += nums2[idx2:]
break
if idx2 < len(nums2):
num2 = nums2[idx2]
else:
tmpL += nums1[idx1:]
break
if num1 < num2:
tmpL.append(num1)
idx1 += 1
elif num1 > num2:
tmpL.append(num2)
idx2 += 1
else:
tmpL.append(num1)
tmpL.append(num2)
idx1 += 1
idx2 += 1
if len(tmpL) % 2:
return tmpL[len(tmpL)//2]
else:
return sum([tmpL[len(tmpL)//2], tmpL[len(tmpL)//2-1]])/2
|
二分法
nums1和nums2是完全排好序的，那么取这两个数组的中位数必然是由前x个nums1中的数加上y个nums2中的数。
我们只需要明白是需要x和y个即可，不需要进行排好序，因为我们不关心取出来的数需要怎么进行排列，我们只关心分割处的数和分别在两个数组中什么位置进行分割的。
中位数和元素个数的关系：
- 对于偶数个元素，中位数是索引为$L//2-1$和$L//2$的两个数的和的平均值
- 对于奇数个元素，中位数是索引为$L//2$的数
因此，为方法进行通用，我们需要从两个数组中取出$L//2$个元素(索引为$L//2-1$)，那么对于偶数可以取分割处的最大值和分割后后半部分的最小值进行求和平均；对于奇数则直接取分割后后半部分的最小值.
数组分割方式：
- 当分割位置位于首位元素前，即此时不取该数组任意元素：分割后的左边没有值，右边最小值为
nums[0]。$L=None;R=nums[0]$
- 当分割位置位于末位元素后，即此时取该数组所有的元素：分割后的左边最大值为
nums[-1],右边没有值。$L=nums[-1];R=None$
- 当分割位置位于首位和末尾之间时：分割后的左边
nums[splitPointIdx]，右边最小值为nums[splitPointIdx+1]。$L=nums[splitPointIdx];R=nums[splitPointIdx+1]$
因为每次分割完后都需要将nums1的L1与nums2的R2，nums1的R1与nums2的L2进行比较，比较的原则是：
- $L1>R2$:说明nums1的分割位置取得过于靠后，需要前移，减小L1的值增大R2的值，因为总个数不变，则nums2的分割位置会后移；
- $L2>R1$:说明nums1的分割位置取得过于靠前，需要后移，增大R1的值减小L1的值，因为总个数不变，则nums2的分割位置会前移；
- $L1<R2 and L2<R1$:此时满足要求，取出来的k个数必然是整个数组的前k个数。
因为是有序数组的分割，必然有L1<=R1,L2<=R2.
因为涉及到数字比较，但是分割情况存在None的情况，为方便比较，当左为None，我们将其设置为整个数组的最小值，当右为None,我们将其设置为整个数组的最大值。这样方法可以实现通用。
二分操作范围：
我们始终对较短的数组进行二分，这样可以减少二分的次数。
起始时，二分位置为整个数组的中间，在迭代过程中，为避免陷入死循环及耗时，需要每次降低二分的范围：
- $L1>R2$:此时nums1的分割位置需要前移了，则将splitPointIdx作为二分范围的最大值边界
- $L2>R1$:此时nums1的分割位置需要后移了，则将splitPointIdx作为二分范围的最小值边界
二分操作每次移动位置最小为1，保证每次都在移动，防止特殊情况陷入死循环。
时间复杂度：$O(n)=log(min(m, n))$空间复杂度：$O(n)=1$
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
| class Solution:
def splitNums(self, nums, cur, minNum, maxNum):
if cur < 0:
return minNum, nums[0]
if cur >= len(nums) - 1:
return nums[-1], maxNum
return nums[cur], nums[cur + 1]
def getResult(self, L1, L2, R1, R2, totalL):
if totalL % 2:
return min(R1, R2)
else:
return (max(L1, L2) + min(R1, R2)) / 2
def findMedianSortedArrays(self, nums1, nums2) -> float:
totalL = len(nums1) + len(nums2)
midIdx = totalL // 2 - 1
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
if len(nums1) == 0:
return self.getResult(nums2[midIdx], nums2[midIdx], nums2[midIdx + 1], nums2[midIdx + 1], totalL)
minNum = min(nums1[0], nums2[0])
maxNum = max(nums1[-1], nums2[-1])
nums1Cur = len(nums1) // 2 - 1
nums2Cur = midIdx - nums1Cur - 1
num1L = 0
num1R = len(nums1)
while True:
L1, R1 = self.splitNums(nums1, nums1Cur, minNum, maxNum)
L2, R2 = self.splitNums(nums2, nums2Cur, minNum, maxNum)
if L1 <= R2 and L2 <= R1:
return self.getResult(L1, L2, R1, R2, totalL)
if L1 > R2:
nums1Cur, num1L = nums1Cur-max(1, (nums1Cur - num1L) // 2), nums1Cur
nums2Cur = midIdx - nums1Cur - 1
if L2 > R1:
nums1Cur, num1R = max(1, (num1R - nums1Cur) // 2)+nums1Cur, nums1Cur
nums2Cur = midIdx - nums1Cur - 1
|
