题： 给定两个长度为m 和 n 有序组数array1 和array2，请找出这个有序数组的中位数。
'''
eg.
[1,3]和[5,6]，中位数是4
[1,2,5,8,9]和[2,3,4,5],中位数是4
'''
### 直接方法，使用内置排序函数sort
# 时间复杂度最高：O((n+m)log(n+m))，空间复杂度：O(n+m)
1 class Solution(object):
2 def findmedian(self,nums1,nums2):
3 nums3=nums1+nums2
4 nums3.sort()
5 return (nums3[len(nums3)//2]+nums3[(len(nums3)-1)//2])/2
6 # eg.
7 nums1=[1,2,5,8,9]
8 nums2=[2,3,4,5]
9 demo=Solution()
10 re=demo.findmedian(nums1,nums2)
11 print(re) # 4.0 再取个整
### 利用双指针将两个数组排序
# 时间复杂度最高：O(n+m)，空间复杂度：O(n+m)
1 class Solution2(object):
2 def findmedian(self,nums1,nums2):
3 nums3=[]
4 j=i=0
5 # 利用双指针将两个数组排序
6 while(i<len(nums1) and j<len(nums2)):
7 if nums1[i]<nums2[j]:
8 nums3.append(nums1[i])
9 i+=1
10 else:
11 nums3.append(nums2[j])
12 j+=1
13 if i==len(nums1) and j!=len(nums2):
14 for x in nums2[j:]:
15 nums3.append(nums2[x])
16 if j==len(nums2) and i!=len(nums1):
17 for x in nums1[i:]:
18 nums3.append(nums1[x])
19 # 返回len(nums3)/2 和(len(nums3)-1)/2 向下取整的均值
20 return (nums3[len(nums3) // 2] + nums3[(len(nums3) - 1) // 2]) / 2
### 采用二分法，再分治处理
# 时间复杂度最高：O(log(min(n+m)))，空间复杂度：O(1)
1 class Solution3:
2 # 定义一个取数组中位数的函数
3 def getmediannum(self,nums):
4 return (nums[len(nums) // 2] + nums[(len(nums) - 1) // 2]) / 2
5
6 def findmedian(self,array1,array2):
7 len1=len(array1)
8 len2=len(array2)
9 # array1为短数组，array2为短数组，不符合则换
10 if len1>len2:
11 return self.findmedian(array2,array1)
12
13 if len1<=2: # 较短的数组长度小于等于2
14 if len2>4: # 较长的数组长度大于4,
15 p1=math.ceil(len2/2)-2 # math.ceil()向上取整
16 array2=array2[p1:-p1] # 取数组中间部分
17 # 合并两部分再排序
18 nums=array1+array2
19 nums.sort()
20 # 可以直接对剩余部分寻找中位数
21 return self.getmediannum(nums)
22
23 p2=math.ceil(len1/2)-1
24 # 较短的数组长度大于2
25 # 当较短的数组的中位数较小时，array1 中位数之前的所有元素就被截去，array2 尾部截去相同的长度，再递归两数组
26 if self.getmediannum(array1)<self.getmediannum(array2):
27 return self.findmedian(array1[p2:],array2[:-p2])
28 else:
29 return self.findmedian(array1[:-p2],array2[p2:])
30 # eg.
31 nums1=[1,2,5,8,9]
32 nums2=[2,3,4,5]
33 demo3=Solution3()
34 re=demo3.findmedian(nums1,nums2)
35 print(re) # 4.0 再取个整
2023-9-10笔记